Segment set（线段并查集）

Segment set

Time Limit : 3000/1000ms (Java/Other) Memory Limit : 32768/32768K (Java/Other)

Total Submission(s) : 12 Accepted Submission(s) : 4

Font: Times New Roman | Verdana | Georgia

Font Size: ← →

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

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

Sample Output

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[1000],dian2[1000];
int par[1005];
int num[1005];
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 0;
    if(diancheng(a,b,c)*diancheng(a,b,d)>0)
        return 0;
     if(diancheng(c,d,b)*diancheng(c,d,a)>0)
     return 0;
        return 1;

}
int main()
{
   int T;
   cin>>T;
   while(T--)
   {
       int n;
       cin>>n;
       for(int i=0;i<=n;i++)
       {
           par[i]=i;
           num[i]=1;
       }
       char a;
       int k=1;
       while(n--)
       {
           cin>>a;
           if(a=='P')
           {
               cin>>dian1[k].x>>dian1[k].y>>dian2[k].x>>dian2[k].y;
               for(int i=1;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 0;
}

一开始没明白为什么跨立实验就可以解决为什么要用快速排斥

应为点乘等于0；有3种可能。

而通过了快速排斥试验，所以上图左边的情况是不可能出现的，只会出现右边的两种情况。

左右2种都是满足相交