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.

In the first line there is an integer t - the number of test
case. For each test case in first line there is an integer n (n<=1000) - the
number of commands.

There are two different commands described in
different format shown below:

P x1 y1 x2 y2 - paint a segment whose
coordinates of the two endpoints are (x1,y1),(x2,y2).
Q k - query the size of
the segment set which contains the k-th segment.

k is between 1 and the
number of segments in the moment. There is no segment in the plane at first, so
the first command is always a P-command.

For each Q-command, output the answer. There is a blank line
between test cases.

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

http://pic002.cnblogs.com/images/2011/287127/2011080416290750.jpg

做之前学习一下

 

 

如果  p1 × p2 为正数，则相对原点(0,0)来说， p1 在p 2 的顺时针方向； 如果p 1  × p2为负数，则p 1 在p 2 的逆时针方向。如果p 1× p2  =0，则p 1和p 2 模相等且共线，方向相同或相反。

#include <iostream>

#include<algorithm>

using namespace std;

struct node

{

    double x,y;

}dian1[],dian2[];

int par[];

int num[];

int findi(int x)

{

    if(par[x]==x)

        return x;

    return par[x]=findi(par[x]);

}

void unioni(int x,int y)

{

    int xx=findi(x);

    int yy=findi(y);

    if(xx!=yy)

    {

        par[xx]=yy;

        num[yy]=num[xx]+num[yy];

    }

}

double diancheng(node a,node b,node c)

{

    return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);

}

int panduan(node a,node b,node c, node d)

{

    int minpx=min(a.x,b.x);

    int minpy=min(a.y,b.y);

    int minqx=min(c.x,d.x);

    int minqy=min(c.y,d.y);

    int minux=max(minpx,minqx);

    int minuy=max(minpy,minqy);

    int maxpx=max(a.x,b.x);

    int maxpy=max(a.y,b.y);

    int maxqx=max(c.x,d.x);

    int maxqy=max(c.y,d.y);

    int maxux=min(maxpx,maxqx);

    int maxuy=min(maxpy,maxqy);

    if(minux>maxux||minuy>maxuy)

        return ;

    if(diancheng(a,b,c)*diancheng(a,b,d)>)

        return ;

     if(diancheng(c,d,b)*diancheng(c,d,a)>)

     return ;

        return ;

}

int main()

{

   int T;

   cin>>T;

   while(T--)

   {

       int n;

       cin>>n;

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

       {

           par[i]=i;

           num[i]=;

       }

       char a;

       int k=;

       while(n--)

       {

           cin>>a;

           if(a=='P')

           {

               cin>>dian1[k].x>>dian1[k].y>>dian2[k].x>>dian2[k].y;

               for(int i=;i<k;i++)

               {

                   if(panduan(dian1[i],dian2[i],dian1[k],dian2[k]))

                   {

                       unioni(i,k);

                   }

               }

               k++;

           }

        else

        {

            int p;

            cin>>p;

            int pp=findi(p);

            cout<<num[pp]<<endl;

        }

       }

       if(T)

        cout<<endl;

   }

    return ;

}