HDU HDU1558 Segment set（并查集+判断线段相交）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1558

解题报告：首先如果两条线段有交点的话，这两条线段在一个集合内，如果a跟b在一个集合内，b跟c在一个集合内，那么a跟c在一个集合内。在一个平面上，有两种操作：

P：在这个平面上添加一条线段

Q k：询问添加的第k条线段所在的那个集合有多少条线段

用并查集，然后就是要判断一下线段有没有交点。还有就是题目要求两个test之间要有空行，为此我还PE了一次。

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<iostream>
  4 #include<algorithm>
  5 #include<cmath>
  6 using namespace std;
  7 const int maxn = 1005;
  8 const double eps = 1e-6;
  9 struct point
 10 {
 11     double x,y;
 12     point(double x = 0,double y = 0):x(x),y(y) {}
 13     inline friend point operator + (point p1,point p2)
 14     {
 15         return point(p1.x+p2.x,p1.y+p2.y);
 16     }
 17     inline friend point operator - (point p1,point p2)
 18     {
 19         return point(p1.x-p2.x,p1.y-p2.y);
 20     }
 21 }pos[maxn];
 22 struct line
 23 {
 24     point s,e;
 25     int flag;
 26 }L[maxn];
 27 int pre[maxn];
 28 int find(int d)
 29 {
 30     return pre[d] == d? d:pre[d] = find(pre[d]);
 31 }
 32 inline double dot(point p1,point p2)    //求叉积
 33 {
 34     return p1.x*p2.y - p2.x*p1.y;
 35 }
 36 int judge(point p1,point p2,point p3,point p4)    //判断线段没有没交点
 37 {
 38     double temp1 = dot(p1-p3,p4-p3) * dot(p2-p3,p4-p3);
 39     double temp2 = dot(p3-p1,p2-p1) * dot(p4-p1,p2-p1);
 40     if((temp1 < 0 || fabs(temp1) < eps) && (temp2 < 0 || fabs(temp2) < eps)) return 1;
 41     return 0;
 42 }
 43 int T,n,m;
 44 void push(line t,line* L,int m)
 45 {
 46     for(int i = 1;i < m;++i)
 47     if(judge(L[i].s,L[i].e,t.s,t.e))
 48     {
 49         pre[find(t.flag)] = find(L[i].flag);
 50     //    break;
 51     }
 52     L[m] = t;
 53 }
 54 int query(int k)
 55 {
 56     int temp = find(k),ans = 0;
 57     for(int i = 1;i <= m;++i)
 58     if(find(i) == temp)
 59     ans++;
 60     return ans;
 61 }
 62 int main()
 63 {
 64 //    freopen("in","r",stdin);
 65     double x1,y1,x2,y2;
 66     scanf("%d",&T);
 67     for(int l = 0;l < T;++l)
 68     {
 69         if(l) puts("");
 70         scanf("%d",&n);
 71         for(int i = 0;i <= 1000;++i)  //初始化并查集
 72         pre[i] = i;
 73         char oper[5];
 74         m = 0;   //初始化当前线段的数量
 75         while(n--)
 76         {
 77             scanf("%s",oper);
 78             if(oper[0] == 'P')
 79             {
 80                 line temp;
 81                 scanf("%lf%lf%lf%lf",&temp.s.x,&temp.s.y,&temp.e.x,&temp.e.y);
 82                 temp.flag = ++m;
 83                 push(temp,L,m);
 84             }
 85             else if(oper[0] == 'Q')
 86             {
 87                 int k;
 88                 scanf("%d",&k);
 89                 printf("%d
",query(k));
 90             }
 91         }
 92 //        for(int i = 1;i <= m;++i)
 93 //        {
 94 //            for(int j = 1;j <= m;++j)
 95 //            printf(judge(L[i].s,L[i].e,L[j].s,L[j].e)? "1 ":"0 ");
 96 //            printf("
");
 97 //        }
 98     }
 99     return 0;
100 }

View Code