判断两个线段是否相交

题目

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

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

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

P x1 y1 x2 y2 - 绘制两个端点坐标为（x1，y1），（x2，y2）的线段。
Q k - 查询包含第k个分段的分段集合的大小。

k在1和当前片段的数量之间。起初飞机上没有任何部分，所以第一个命令总是一个P命令。
产量对于每个Q命令，输出答案。测试用例之间有空行

。示例输入

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
示例输出

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

对于线段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<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
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<m;j++)
                {
                    int xx=find(j);
                    int yy=find(m);
                    if(xx!=yy)
                    {
                        if(pan(mp[m],mp[j]))
                        {
                            pre[xx]=yy;
                            num[yy]+=num[xx];
                        }
                    }
                }
            }
            else{
                int x;
                scanf("%d",&x);
                x=find(x);
                printf("%d
",num[x]);
            }
        }
        if(t!=0)
        printf("
");
    }
}