题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1558
解题报告：首先如果两条线段有交点的话，这两条线段在一个集合内，如果a跟b在一个集合内，b跟c在一个集合内，那么a跟c在一个集合内。在一个平面上，有两种操作：
P：在这个平面上添加一条线段
Q k：询问添加的第k条线段所在的那个集合有多少条线段
用并查集，然后就是要判断一下线段有没有交点。还有就是题目要求两个test之间要有空行，为此我还PE了一次。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn = ;
const double eps = 1e-;
struct point
{
double x,y;
point(double x = ,double y = ):x(x),y(y) {}
inline friend point operator + (point p1,point p2)
{
return point(p1.x+p2.x,p1.y+p2.y);
}
inline friend point operator - (point p1,point p2)
{
return point(p1.x-p2.x,p1.y-p2.y);
}
}pos[maxn];
struct line
{
point s,e;
int flag;
}L[maxn];
int pre[maxn];
int find(int d)
{
return pre[d] == d? d:pre[d] = find(pre[d]);
}
inline double dot(point p1,point p2) //求叉积
{
return p1.x*p2.y - p2.x*p1.y;
}
int judge(point p1,point p2,point p3,point p4) //判断线段没有没交点
{
double temp1 = dot(p1-p3,p4-p3) * dot(p2-p3,p4-p3);
double temp2 = dot(p3-p1,p2-p1) * dot(p4-p1,p2-p1);
if((temp1 < || fabs(temp1) < eps) && (temp2 < || fabs(temp2) < eps)) return ;
return ;
}
int T,n,m;
void push(line t,line* L,int m)
{
for(int i = ;i < m;++i)
if(judge(L[i].s,L[i].e,t.s,t.e))
{
pre[find(t.flag)] = find(L[i].flag);
// break;
}
L[m] = t;
}
int query(int k)
{
int temp = find(k),ans = ;
for(int i = ;i <= m;++i)
if(find(i) == temp)
ans++;
return ans;
}
int main()
{
// freopen("in","r",stdin);
double x1,y1,x2,y2;
scanf("%d",&T);
for(int l = ;l < T;++l)
{
if(l) puts("");
scanf("%d",&n);
for(int i = ;i <= ;++i) //初始化并查集
pre[i] = i;
char oper[];
m = ; //初始化当前线段的数量
while(n--)
{
scanf("%s",oper);
if(oper[] == 'P')
{
line temp;
scanf("%lf%lf%lf%lf",&temp.s.x,&temp.s.y,&temp.e.x,&temp.e.y);
temp.flag = ++m;
push(temp,L,m);
}
else if(oper[] == 'Q')
{
int k;
scanf("%d",&k);
printf("%d\n",query(k));
}
}
// for(int i = 1;i <= m;++i)
// {
// for(int j = 1;j <= m;++j)
// printf(judge(L[i].s,L[i].e,L[j].s,L[j].e)? "1 ":"0 ");
// printf("\n");
// }
}
return ;
}