hdu 1558 Segment set 计算几何+并查集★

  1 #include <cstdio>
  2 #include <iostream>
  3 #include <string.h>
  4 using namespace std;
  5 
  6 const double EPS = 1e-10;
  7 #define MAX 1001
  8 
  9 struct point    //点
 10 {
 11     double x,y;
 12 };
 13 
 14 struct line     //线
 15 {
 16     point a,b;
 17 }l[MAX];
 18 
 19 int father[MAX],num[MAX];
 20 double Max(double a,double b)   {return a>b?a:b;}
 21 double Min(double a,double b)   {return a>b?b:a;}
 22 
 23 // 判断两线段是否相交（非规范相交）
 24 bool inter(line l1,line l2)
 25 {
 26     point p1,p2,p3,p4;
 27     p1=l1.a;p2=l1.b;
 28     p3=l2.a;p4=l2.b;
 29 
 30     if( Min(p1.x,p2.x)>Max(p3.x,p4.x) ||
 31        Min(p1.y,p2.y)>Max(p3.y,p4.y) ||
 32        Min(p3.x,p4.x)>Max(p1.x,p2.x) ||
 33        Min(p3.y,p4.y)>Max(p1.y,p2.y) )
 34         return 0;   //直接没有相交
 35     double k1,k2,k3,k4;
 36     k1 = (p2.x-p1.x)*(p3.y-p1.y) - (p2.y-p1.y)*(p3.x-p1.x);
 37     k2 = (p2.x-p1.x)*(p4.y-p1.y) - (p2.y-p1.y)*(p4.x-p1.x);
 38     k3 = (p4.x-p3.x)*(p1.y-p3.y) - (p4.y-p3.y)*(p1.x-p3.x);
 39     k4 = (p4.x-p3.x)*(p2.y-p3.y) - (p4.y-p3.y)*(p2.x-p3.x);
 40     return (k1*k2<=EPS && k3*k4<=EPS);
 41 }
 42 
 43 //初始化函数
 44 void Init(int n)
 45 {
 46     int i;
 47     for(i=1;i<=n;i++)
 48     {
 49         father[i]=i;
 50         num[i]=1;
 51     }
 52 }
 53 
 54 int Find(int x)
 55 {
 56     while(father[x]!=x)
 57         x=father[x];
 58     return x;
 59 }
 60 
 61 void combine(int a,int b)
 62 {
 63     int temp_a,temp_b;
 64     temp_a=Find(a);
 65     temp_b=Find(b);
 66 
 67     // 在合并集合的时候，相应集合所含的个数也要合并
 68     if(temp_a!=temp_b)
 69     {
 70         father[temp_a]=temp_b;
 71         num[temp_b]+=num[temp_a];
 72     }
 73 }
 74 
 75 int main()
 76 {
 77     int test,i,n,k,js;
 78     char c;
 79     cin>>test;
 80     while(test--)
 81     {
 82         js=0;
 83         cin>>n;
 84         Init(n);
 85         while(n--)
 86         {
 87             cin>>c;
 88             // 判断是P还是Q
 89             if(c=='P')
 90             {
 91                 ++js;
 92                 cin>>l[js].a.x>>l[js].a.y>>l[js].b.x>>l[js].b.y;
 93 
 94                 // 判断该线段与之前线段是否相交，相交则合并
 95                 for(i=1;i<js;++i)
 96                 {
 97                     if( inter(l[js],l[i]) )
 98                         combine(js,i);
 99                 }
100             }
101             else
102             {
103                 cin>>k;
104                 cout<<num[Find(k)]<<endl;
105             }
106         }
107         // 格式！！！很重要，最后一组测试数据后无空行
108         if(test)   cout<<endl;
109     }
110     return 0;
111 }