http://acm.hdu.edu.cn/showproblem.php?pid=1558
//1270982 2009-04-14 20:14:31 Accepted 1558 390MS 264K 2589 B C++ no way
#include<iostream>
#define min(x,y) (x < y ? x : y)
#define max(x,y) (x > y ? x : y)
using namespace std;
struct Point
  {
double x;
double y;
};
struct Segement
  {
Point lefts;
Point rights;
};

int sets[1001];
Segement segs[1001];

int find(int x)
  {
int r,i,j;
r = x;
while(r != sets[r])//寻根
r = sets[r];
i = r;
while(i != sets[i])//路径压缩
 {
j = sets[i];
sets[i] = r;
i = j;
}
return r;
}

void merge(int a,int b)
  {
a = find(a);
b = find(b);
if(a != b)
sets[a] = b;
}

 /**//////////////////////////////////////////////////////////////////////////////// //判断两条线段是否相交
 /**//////////////////////////////////////////////////////////////////////////////// double direction(Point p0,Point p1,Point p2)
  {
return (p2.x-p0.x)*(p1.y-p0.y)-(p1.x-p0.x)*(p2.y-p0.y);
}

bool on_segment(Point p0,Point p1,Point p2)
  {
if((min(p0.x,p1.x)<=p2.x && p2.x<=max(p0.x,p1.x)) && (min(p0.y,p1.y)<=p2.y && p2.y<=max(p0.y,p1.y)))
return true;
return false;
}

bool Segment_intersect(Point p1,Point p2,Point p3,Point p4)
  {
double d1,d2,d3,d4;
d1 = direction(p3,p4,p1);
d2 = direction(p3,p4,p2);
d3 = direction(p1,p2,p3);
d4 = direction(p1,p2,p4);
if(((d1>0 && d2<0)||(d1<0 && d2>0)) && ((d3>0 && d4<0)||(d3<0&&d4>0)))
return true;
else if(d1==0 && on_segment(p3,p4,p1))
return true;
else if(d2==0 && on_segment(p3,p4,p2))
return true;
else if(d3==0 && on_segment(p1,p2,p3))
return true;
else if(d4==0 && on_segment(p1,p2,p4))
return true;
return false;
}
 /**/////////////////////////////////////////////////////////////////////////////////////// int main()
  {
int t,n,k,i,j,num;
char op;
cin>>t;
while(t--)
 {
k=1;
scanf("%d",&n);
while(n--)
 {
cin>>op;
if(op == 'P')
 {
scanf("%lf%lf%lf%lf",&segs[k].lefts.x,&segs[k].lefts.y,&segs[k].rights.x,&segs[k].rights.y);
sets[k] = k;
for(i=1;i<k;i++)
 {
if(Segment_intersect(segs[i].lefts,segs[i].rights,segs[k].lefts,segs[k].rights))//第i条线段与第k条线段相交
 {
merge(i,k);
}
}
k++;
}
else
 {
scanf("%d",&i);
i = find(i);
for(num=0,j=1;j<k;j++)
if(find(j)==i)
num++;
printf("%d\n",num);
}
}
 /**//*
cout<<k<<endl;
for(i=1;i<k-1;i++)
for(int j=i+1;j<k;j++)
cout<<Segment_intersect(segs[i].lefts,segs[i].rights,segs[j].lefts,segs[j].rights)<<" ";
cout<<endl;
*/
if(t>0)
printf("\n");
}
return 0;
}
|