题目

段和与其连接的所有段组成段组。段集的大小是其中的段的数量。问题是要找到一些段集的大小。 

输入在第一行中有一个整数t - 测试用例的数量。对于第一行中的每个测试用例，都有一个整数n（n <= 1000） - 命令的数量。 

有两种不同的命令以不同的格式描述如下： 

P x1 y1 x2 y2 - 绘制两个端点坐标为（x1，y1），（x2，y2）的线段。 

Q k - 查询包含第k个分段的分段集合的大小。 

k在1和当前片段的数量之间。起初飞机上没有任何部分，所以第一个命令总是一个P命令。 

产量对于每个Q命令，输出答案。测试用例之间有空行

。示例输入

110P 1.00 1.00 4.00 2.00P 1.00 -2.00 8.00 4.00Q 1P 2.00 3.00 3.00 1.00Q 1Q 3P 1.00 4.00 8.00 2.00Q 2P 3.00 3.00 6.00 -2.00Q 5 示例输出

12225 题意：是求第几个点相交的几个直线个数 判断两个线段是否相交

对于线段A，B，如果 线段A与直线B相交 ，线段B与直线A相交 ，那么就可以认为线段A 和线段B相交。

关键问题是：如何判断直线AB是否与线段CD相交呢？

设直线AB的方程为：f(x,y) = 0,直线方程可以通过两点式求得。

当C和D点不在直线的同侧时，直线AB必然与线段CD相交，也就是说直线AB与线段CD相交的条件为：f(C) * f(D) <= 0。

 

注意：算每个集合中有多少个元素，只要再单独维护一个数组，开始都是值为1，因为开始集合中都只有本身，然后合并一个集合的时候把数组值相加就行

 

代码：

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;struct sss{    double x1,x2,y1,y2;}mp[1001];int t,n;int pre[1001];int num[1001];int suan(struct sss x,struct sss y){    double f1=(y.x1-x.x1)/(x.x1-x.x2)-(y.y1-x.y1)/(x.y1-x.y2);    double f2=(y.x2-x.x1)/(x.x1-x.x2)-(y.y2-x.y1)/(x.y1-x.y2);    if(f1*f2<=0)    return 1;    return 0;}int pan(struct sss x,struct sss y){    if(!suan(x,y))    return 0;    if(!suan(y,x))    return 0;    return 1;}int find(int x){    if(x==pre[x]) return x;    return pre[x]=find(pre[x]);}int main(){    scanf("%d",&t);    while(t--)    {        char c;        int m=0;        scanf("%d",&n);        for(int i=1;i<=n;i++)         pre[i]=i,num[i]=1;         for(int i=1;i<=n;i++)        {            cin>>c;            if(c=='P')            {                m++;                cin>>mp[m].x1>>mp[m].y1>>mp[m].x2>>mp[m].y2;                for(int j=1;j