Hdu 1558 Segment set（并查集+几何）

思路：判断线段相交（注意端点相交），若相交并入同一集合。

#include<cstdio>#include<queue>#include<cmath>#include<cstring>#include<iostream>#include<algorithm>#define debuusing namespace std;const double eps=1e-10;const int maxn=1e3+50;const int INF=0x3f3f3f3f;struct Point{    double x,y;    Point(double x=0,double y=0):x(x),y(y) {}};struct Line{    Point x,y;    Line(Point x=NULL,Point y=NULL):x(x),y(y) {}};typedef Point Vector;Vector Operator - (const Point &A,const Point &B){    return Vector(A.x-B.x,A.y-B.y);}int n,tot;Line L[maxn];int fa[maxn],w[maxn];int dcmp(double x){    if(fabs(x)<eps) return 0;    else return x<0?-1:1;}bool operator == (const Point &a, const Point &b){    return dcmp(a.x - b.x) == 0 && dcmp(a.y - b.y) == 0;}double Dot(const Vector &A,const Vector &B){    return A.x*B.x+A.y*B.y;}double Cross(const Vector &A,const Vector &B){    return A.x*B.y-A.y*B.x;}bool SegmentProperIntersection(const Point &a1, const Point &a2, const Point &b1, const Point &b2){    double c1 = Cross(a2 - a1, b1 - a1), c2 = Cross(a2 - a1, b2 - a1), c3 = Cross(b2 - b1, a1 - b1), c4 = Cross(b2 - b1, a2 - b1);    return dcmp(c1) * dcmp(c2) < 0 && dcmp(c3) * dcmp(c4) < 0;}bool OnSegment(Point p,Point a1,Point a2){    return dcmp(Cross(a1-p,a2-p))==0&&dcmp(Dot(a1-p,a2-p))<0;}int Find(int x){    return fa[x]==x?x:fa[x]=Find(fa[x]);}void Union(int x,int y){    fa[x]=y;    w[y]+=w[x];}void init(){    tot=0;    for(int i=1; i<=n; i++)    {        w[i]=1;        fa[i]=i;    }}int check(Point p,Point x,Point y){    return p==x||p==y;}int main(){#ifdef debug    freopen("in.in","r",stdin);#endif // debug    int t,cas=0;    scanf("%d",&t);    while(t--)    {        cas++;        if(cas!=1) printf("/n");        scanf("%d",&n);        init();        for(int i=0; i<n; i++)        {            char ch;            getchar();            scanf("%c",&ch);            if(ch=='P')            {                tot++;                double x1,y1,x2,y2;                scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);                Point tmp1=Point(x1,y1),tmp2=Point(x2,y2);                L[tot]=Line(tmp1,tmp2);                for(int j=1; j<tot; j++)                {                    if(SegmentProperIntersection(L[tot].x,L[tot].y,L[j].x,L[j].y)||                            OnSegment(L[tot].x,L[j].x,L[j].y)||OnSegment(L[tot].y,L[j].x,L[j].y)||                            check(L[tot].x,L[j].x,L[j].y)||check(L[tot].y,L[j].x,L[j].y))                    {                        //cout<<tot<<" "<<j<<endl;                        int xx=Find(tot),yy=Find(j);                        if(xx!=yy)                        {                            Union(xx,yy);                        }                    }                }            }            else            {                int k;                scanf("%d",&k);                printf("%d/n",w[Find(k)]);            }        }    }    return 0;}