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; }
|