HOJ 1558 Segment set (判断线段相交，并查集)

判断线段相交，并查集
本题要点：
1、每次 P 操作，就是加入一条线段，需要判断当前加入的线段 k ，和 前面 1 ~ k - 1 条线段，
是否相交。如果相交，做并查集 merge 操作。
每次 Q 查询，输出第k条线段所在并查集 的 sum 即可。
2、需要注意的是，每连个 test 之间有 空行。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
using namespace std;
double eps = 1e-6;
const int MaxN = 1010;
int T, n;
int fa[MaxN], sum[MaxN];
char cmd[3];struct Point
{
    double x, y;
};struct Line
{
    Point a, b;
} line[MaxN];double cross(Point a, Point b, Point c)
{
    return (a.x - c.x) * (b.y - c.y) - (a.y - c.y) * (b.x - c.x);
}bool isCross(Point a, Point b, Point c, Point d)
{
    if (cross(c, b, a) * cross(b, d, a) < 0) return false;if (cross(a, d, c) * cross(d, b, c) < 0) return false;return true;
}int get(int x)
{
    if(fa[x] == x)return x;return fa[x] = get(fa[x]);
}void merge(int x, int y)
{
    int fax = get(x), fay = get(y);if(fax != fay){
    fa[fax] = fay;sum[fay] += sum[fax];}
}int main()
{
    int id;scanf("%d", &T);while(T--){
    scanf("%d", &n);for(int i = 1; i <= n; ++i){
    fa[i] = i, sum[i] = 1;}int k = 0;while(n--){
    scanf("%s", cmd);if(cmd[0] == 'P'){
    ++k;scanf("%lf%lf%lf%lf", &line[k].a.x, &line[k].a.y, &line[k].b.x, &line[k].b.y);	for(int i = 1; i < k; i++){
    if(isCross(line[i].a, line[i].b, line[k].a, line[k].b)){
    merge(i, k);}}}else{
    scanf("%d", &id);printf("%d\n", sum[get(id)]);}}if(T)printf("\n");}return 0;
}/* 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 */