Segment set

Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 3907    Accepted Submission(s): 1471

A segment and all segments which are connected with it compose a segment set. The size of a segment set is the number of segments in it. The problem is to find the size of some segment set.

1

10

P 1.00 1.00 4.00 2.00

P 1.00 -2.00 8.00 4.00

Q 1

P 2.00 3.00 3.00 1.00

Q 1

Q 3

P 1.00 4.00 8.00 2.00

Q 2

P 3.00 3.00 6.00 -2.00

Q 5

1

2

2

2

5

题目大意：在一个平面直角坐标系里面，通过P操作不断的增加线段，假设两个线段有相交。就表明他们是一个集合里面的。Q操作询问当前情况下第k条线段所在的集合里面有几条线段。

并查集的题目，可是我认为主要考几何。我開始能够想到。通过推断两条线段是否有交点，假设有就放在一个集合里面。这么想的确非常easy，可是做起来真的十分麻烦。。

假设对于两条线段，能够通过简单计算得到两者的交点x0=(b2-b1)/(k1-k2)，还有y0。

那么我仅仅要推断x0,y0是否在线段相交的地方就可以。可是还要注意，这个交点是从k1,k2得到的。所以假设k1,k2不存在，又要分情况讨论。

下面是我的代码，感觉好像还有遗漏的地方，尽管的确是AC了。

#include<stdio.h>

#include<string.h>

int p[10000],sum[10000];

double x1[1005],x2[1005],y1[1005],y2[1005];

void init(int x)

{

    int i;

    for(i=0;i<=x;i++)

    p[i]=i;

    for(i=0;i<=x;i++)

    sum[i]=1;

}

int findroot(int x)

{

    int r=x;

    while(r!=p[r])

    r=p[r];

    int i,j;

    i=x;

    while(i!=r)

    {

        j=p[i];

        p[i]=r;

        i=j;

    }

    return r;

}

void merge(int x,int y)

{

    int fx=findroot(x);

    int fy=findroot(y);

    if(fx!=fy){

        p[fx]=fy;

        sum[fy]+=sum[fx];

            }

}

double jiaodian(double x1,double y1,double x2,double y2,double x3,double y3,double x4,double y4)

{

    if(x1==x2&&x3!=x4){             //k1不存在,k2存在

         double k2=(y3-y4)/(x3-x4);

        double y=k2*(x1-x3)+y3;

        if((y>=y1&&y<=y2)||(y>=y2&&y<=y1))return 1;

        else return 0;

    }

   else if(x3==x4&&x1!=x2){           //k2不存在，k1存在

        double k1=(y1-y2)/(x1-x2);

        double y=k1*(x3-x1)+y1;

        if((y>=y3&&y<=y4)||(y>=y4&&y<=y3))return 1;

        else return 0;

    }

   else if(x1==x2&&x3==x4){

        if(x1==x3&&((y1>=y3&&y1<=y4)||(y1>=y4&&y1<=y3)||(y2>=y4&&y2<=y3)||(y2>=y3&&y2<=y4)))return 1;

        else return 0;

    }

    double k1=(y1-y2)/(x1-x2);

     double k2=(y3-y4)/(x3-x4);

    double b1=(x1*y2-x2*y1)/(x1-x2);

    double b2=(x3*y4-x4*y3)/(x3-x4);

    double x=(b2-b1)/(k1-k2);

    double y=k1*(x-x1)+y1;

    if(((x>=x1&&x<=x2)||(x>=x2&&x<=x1))&&((y>=y1&&y<=y2)||(y>=y2&&y<=y1))&&

    ((x>=x3&&x<=x4)||(x>=x4&&x<=x3))||((y>=y3&&y<=y4)&&(y>=y4&&y<=y3)))return 1;

     return 0;

}

void isconnect(int x)

{

    int i;

    for(i=1;i<=x;i++)

  {

      if(jiaodian(x1[i],y1[i],x2[i],y2[i],x1[x],y1[x],x2[x],y2[x])){merge(i,x);}

  }

  return ;

}

int main()

{

    int t,n,i,j,k,m,cnt,q;

    char c[10];

    scanf("%d",&t);

    while(t--)

    {

        q=1;

        scanf("%d",&n);

        init(n);

        cnt=1;

        for(i=1;i<=n;i++)

        {

            scanf("%s",c);

            if(c[0]=='P')

            {

            scanf("%lf%lf%lf%lf",&x1[q],&y1[q],&x2[q],&y2[q]);

            if(i>1){

             isconnect(q);

            }

            q++;

            }

            if(c[0]=='Q'){

                scanf("%d",&k);

                int s=findroot(k);

                cnt=sum[s];

                printf("%d\n",cnt);

            }

        }

            if(t>0)printf("\n");

    }

    return 0;

}