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

 

Sample Output

 

Author

LL

 

Source

#pragma comment(linker, "/STACK:1024000000,1024000000")

#include<iostream>

#include<cstdio>

#include<cmath>

#include<string>

#include<queue>

#include<algorithm>

#include<stack>

#include<cstring>

#include<vector>

#include<list>

#include<bitset>

#include<set>

#include<map>

#include<time.h>

using namespace std;

#define LL long long

#define bug(x)  cout<<"bug"<<x<<endl;

const int N=1e3+,M=2e6+,inf=1e9+;

const LL INF=1e18+,mod=,MOD=;

const double eps=1e-,pi=(*atan(1.0));

int sgn(double x)

{

    if(fabs(x) < eps)return ;

    if(x < )return -;

    else return ;

}

struct Point

{

    double x,y;

    Point() {}

    Point(double _x,double _y)

    {

        x = _x;

        y = _y;

    }

    Point operator -(const Point &b)const

    {

        return Point(x - b.x,y - b.y);

    }

    //叉积

    double operator ^(const Point &b)const

    {

        return x*b.y - y*b.x;

    }

//点积

    double operator *(const Point &b)const

    {

        return x*b.x + y*b.y;

    }

//绕原点旋转角度B（弧度值），后x,y的变化

    void transXY(double B)

    {

        double tx = x,ty = y;

        x= tx*cos(B) - ty*sin(B);

        y= tx*sin(B) + ty*cos(B);

    }

};

struct Line

{

    Point s,e;

    Line() {}

    Line(Point _s,Point _e)

    {

        s = _s;

        e = _e;

    }

//两直线相交求交点 //第一个值为0表示直线重合，为1表示平行，为0表示相交,为2是相交 //只有第一个值为2时，交点才有意义

    pair<int,Point> operator &(const Line &b)const

    {

        Point res = s;

        if(sgn((s-e)^(b.s-b.e)) == )

        {

            if(sgn((s-b.e)^(b.s-b.e)) == ) return make_pair(,res);//重合

            else return make_pair(,res);//平行

        }

        double t = ((s-b.s)^(b.s-b.e))/((s-e)^(b.s-b.e));

        res.x += (e.x-s.x)*t;

        res.y += (e.y-s.y)*t;

        return make_pair(,res);

    }

};

bool inter(Line l1,Line l2)

{

    return

        max(l1.s.x,l1.e.x) >= min(l2.s.x,l2.e.x) &&

        max(l2.s.x,l2.e.x) >= min(l1.s.x,l1.e.x) &&

        max(l1.s.y,l1.e.y) >= min(l2.s.y,l2.e.y) &&

        max(l2.s.y,l2.e.y) >= min(l1.s.y,l1.e.y) &&

        sgn((l2.s-l1.e)^(l1.s-l1.e))*sgn((l2.e-l1.e)^(l1.s-l1.e)) <=  &&

        sgn((l1.s-l2.e)^(l2.s-l2.e))*sgn((l1.e-l2.e)^(l2.s-l2.e)) <= ;

}

char ch[N];

int fa[N],si[N];

int Find(int x)

{

    return x==fa[x]?x:fa[x]=Find(fa[x]);

}

void update(int u,int v)

{

    int x=Find(u);

    int z=Find(v);

    if(x!=z)

    {

        fa[x]=z;

        si[z]+=si[x];

    }

}

Line a[N];

int main()

{

    int T,cas=;

    scanf("%d",&T);

    while(T--)

    {

        if(cas)printf("\n");

        cas++;

        int cnt=;

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

            fa[i]=i,si[i]=;

        int q;

        scanf("%d",&q);

        while(q--)

        {

            scanf("%s",ch);

            if(ch[]=='Q')

            {

                int x;

                scanf("%d",&x);

                int f=Find(x);

                printf("%d\n",si[f]);

            }

            else

            {

                double x1,y1,x2,y2;

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

                Point s(x1,y1),e(x2,y2);

                a[++cnt]=Line(s,e);

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

                    if(inter(a[i],a[cnt]))update(i,cnt);

            }

        }

    }

    return ;

}