1558.txt

杭电acm解题报告2001---2099.

#include <cstdio>
#include <memory>
//using namespace std;
const int Max=1100;

int Parent[Max],Rank[Max],set[Max];
struct Point
{
    double x,y;
}line[Max][2];

bool insertLine(Point a,Point c,Point b,Point d)
{
    double t1,t2, num1, num2,num3,num4;
    num1  = (a.y - c.y)*(d.x - c.x) - (a.x - c.x)*(d.y - c.y);//(d-c)**(a-c)
    num2  = (a.y - c.y)*(b.x - c.x) - (a.x - c.x)*(b.y - c.y);//(b-c)**(a-c)
    
    num3  = (d.y - b.y)*(a.x - b.x) - (d.x - b.x)*(a.y - b.y);//(d-b)**(a-b)
    num4  = (c.x - b.x)*(d.y - b.y) - (c.y - b.y)*(d.x - b.x);//(d-b)**(c-b)
    
    t1=num1*num2;
    t2=num3*num4;
    if( t1<=0 && t2<=0)
        return true;
    else
        return false;
}

int Find(int x)
{
    int temp=x;
    int root,w;
    
    while(Parent[x]!=0)   //搜寻根节点
        x=Parent[x];
    root=x;
    x=temp;
    while(Parent[x]!=0)  //压缩路径
    {
        w=Parent[x];
        Parent[x]=root;
        x=w;
    }
    return root;
}

int Union(int x,int y)
{
    int u,v;
    int root;
    
    u=Find(x);
    v=Find(y);
    if(u==v)    return 0;
    if(Rank[u]<=Rank[v])
    {
        root=Parent[u]=v;
        set[root] += set[u];
        if(Rank[u]==Rank[v])
            Rank[v]++;
    }
    else
        root=Parent[v]=u , set[root] += set[v];;
        
    return root;
}

int main()
{
    int t,n,i,j,seg,k;
    char cmd;
    scanf("%d",&t);
    while(t--)
    {
        memset(Parent,-1,sizeof(Parent));
        memset(Rank,0,sizeof(Rank));
        memset(set,0,sizeof(set));
        k=1;
        scanf("%d",&n);
        for(i=1;i<=n;i++)
        {
            getchar();
            cmd=getchar();
            if(cmd=='P')
            {
                scanf("%lf %lf %lf %lf",&line[k][0].x,&line[k][0].y,&line[k][1].x,&line[k][1].y);
                Parent[k]=0;    set[k]++;
                for(j=1;j<k;j++)
                {
                    if( insertLine(line[k][0],line[k][1],line[j][0],line[j][1]) )
                    {
                        Union(k,j);
                    }
                }
                k++;
            }
            else
            {
                scanf("%d",&seg);
                printf("%d\n",set[ Find(seg) ]);
            }
        }
        if(t!=0)
            printf("\n");
    }
}