Segment set

Problem Description

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.

Input

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.

Output

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

Sample Input

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

Sample Output

题意是要求输入一些线段，判断这些线段连接成几个集合，然后求包含某条线段的集合中的元素个数；

本题主要难关是判断量条线段是否相交，在我这篇文章里有详细介绍判断两条线段相交的方法。http://www.cnblogs.com/sytu/articles/3876585.html;

Notice:二维向量的叉乘公式是 axb=(x1,y1)x(x2,y2)=x1*y2-y1*x2;

下面为AC代码：

 #include<iostream>

 using namespace std;

 #define MIN(x,y) (x < y ? x : y)

 #define MAX(x,y) (x > y ? x : y)

 typedef struct

 {

     double x,y;

 } Point;

 struct LINE

 {

     double x1,x2,y1,y2;

     int flag;

 };

 LINE *line;

 int lineintersect(int a,int b)

 {

     Point p1,p2,p3,p4;

     p1.x=line[a].x1;p1.y=line[a].y1;

     p2.x=line[a].x2;p2.y=line[a].y2;

     p3.x=line[b].x1;p3.y=line[b].y1;

     p4.x=line[b].x2;p4.y=line[b].y2;

     Point tp1,tp2,tp3,tp4,tp5,tp6;

     if ((p1.x==p3.x&&p1.y==p3.y)||(p1.x==p4.x&&p1.y==p4.y)||(p2.x==p3.x&&p2.y==p3.y)||(p2.x==p4.x&&p2.y==p4.y))

         return ;

 //快速排斥试验

 if(MAX(p1.x,p2.x)<MIN(p3.x,p4.x)||MAX(p3.x,p4.x)<MIN(p1.x,p2.x)||MAX(p1.y,p2.y)<MIN(p3.y,p4.y)||MAX(p3.y,p4.y)<MIN(p1.y,p2.y))

             return ;

 //跨立试验

     tp1.x=p1.x-p3.x;

     tp1.y=p1.y-p3.y;

     tp2.x=p4.x-p3.x;

     tp2.y=p4.y-p3.y;

     tp3.x=p2.x-p3.x;

     tp3.y=p2.y-p3.y;//从这到上面是一组的向量

     tp4.x=p2.x-p4.x;//下面是一组的向量

     tp4.y=p2.y-p4.y;

     tp5.x=p2.x-p3.x;

     tp5.y=p2.y-p3.y;

     tp6.x=p2.x-p1.x;

     tp6.y=p2.y-p1.y;

     if ((tp1.x*tp2.y-tp1.y*tp2.x)*(tp2.x*tp3.y-tp2.y*tp3.x)>=) //此处用到了叉乘公式

     {

         if((tp4.x*tp6.y-tp4.y*tp6.x)*(tp6.x*tp5.y-tp6.y*tp5.x)>=)

             return ;

     }

 return ;

 }

 int find(int x)

 {

     if(>line[x].flag)return x;

     return line[x].flag=find(line[x].flag);

 }

 void Union(int a,int b)

 {

     int fa=find(a);

     int fb=find(b);

     if(fa==fb)return;

     int n1=line[fa].flag;

     int n2=line[fb].flag;

     if(n1>n2)

     {

         line[fa].flag=fb;

         line[fb].flag+=n1;

     }

     else

     {

         line[fb].flag=fa;

         line[fa].flag+=n2;

     }

 }

 void throwinto(int n)

 {

     if(n>)

     {

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

         {

             if(lineintersect(i,n))

             Union(i,n);

         }

     }

 }

 int main()

 {

     int t;

     cin>>t;

     int n,q;

     int cn=t;

     while(t--)

     {

         int cnt=;

         cin>>n;

         line=new LINE[n+];

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

         {

             line[i].flag=-;

         }

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

         {

             char sj;

             cin>>sj;

             if(sj=='P')

             {

                 cin>>line[cnt].x1>>line[cnt].y1>>line[cnt].x2>>line[cnt].y2;

                 throwinto(cnt);

                 cnt++;

             }

             else if(sj=='Q')

             {

                 cin>>q;

                 int re=find(q);

                 cout<<-line[re].flag<<endl;

             }

         }

         if(t>)cout<<endl;//注意格式问题，容易出错

     }

     return ;

 }

巴特西

ACM1558两线段相交判断和并查集

Segment set

最新文章

热门文章