题目地址:http://acm.hdu.edu.cn/showproblem.php?pid=1558

题目描述

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.
http://acm.hdu.edu.cn/data/images/C50-1004-1.jpg

思路

好坑的并查集!卡在线段相交,主要就是每次添加线段并判断两线段是否相交,相交就放在一个集合(一棵树)中,然后查询的时候,看看有那些线段和查询的线段同集合(树)即可。

AC代码

/*************************************************************************
    > File Name: 1558.cpp
      > Author: Netcan
      > Blog: http://www.netcan.xyz
      > Mail: 1469709759@qq.com
      > Created Time: 2015-07-04 Sat 22:02:28 CST
 ************************************************************************/

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <sstream>
#include <deque>
#include <functional>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <stack>
#include <set>
#include <numeric>
#include <utility>
#include <cstring>
using namespace std;
const int _max = 1000+10;
struct point { // 点
    double x, y;
};
struct line { // 线段
    point s, e;
};
double s(point &a, point &b, point &c) { // 据说是三角形有向面积判断顺逆时针,若$S>0$则说明 $abc$ 三点逆时针排列,$S=0$则说明三点共线,$S<0$则说明 $abc$ 三点呈现顺时针排列。
    return a.x*b.y + b.x*c.y + c.x*a.y - a.x*c.y - c.x*b.y - b.x*a.y;
}
bool connected(point &a, point &b, point &c, point &d) { // 判断两直线 $ab$ 和 $cd$ 是否相交。
    if(s(a, b, c)*s(a,b,d)<=0 && s(d,c,a)*s(d,c,b)<=0) return true;
    return false;
}
line line[_max]; // 线段
int Set[_max], height[_max]; // 集合/深度

int find(int x) { // 查找根节点/路径压缩
    if(x==Set[x]) return x;
    else return Set[x] = find(Set[x]);
}
void merge(int a, int b) { // 合并+求深度(可省略)
    int fx = find(a);
    int fy = find(b);
    if(fx!=fy) {
        if(height[fx]<height[fy]) Set[fx] = fy;
        else Set[fy] = fx;
        if(height[a] == height[b])
            ++height[a];
    }
}
void Q(int n) { // 判断序号1-n的相交情况,相交的放在一个集合(合并)
    for(int i=1; i<n; ++i)
        if(connected(line[i].s, line[i].e, line[n].s, line[n].e)) // 相交合并
            merge(i, n);
}

int main()
{
#ifdef Oj
    freopen("1558.in", "r", stdin);
#endif
    int T;
    scanf("%d", &T);
    while(T--) {
        int N;
        scanf("%d", &N);
        for(int i=1; i<=N; ++i) { // 初始化
            Set[i] = i;
            height[i] = 0;
        }
        int lines = 0; // 线段数
        for(int i=1; i<=N; ++i) {
            char cmd;
            getchar();
            scanf("%c", &cmd);
            if(cmd == 'P') {
                ++lines;
                scanf("%lf%lf%lf%lf", &line[lines].s.x, &line[lines].s.y, &line[lines].e.x, &line[lines].e.y);
                Q(lines); // 依次判断相交情况

            }
            else {
                int k; // 查询的线段编号
                int ans = 0;
                scanf("%d", &k);
                for(int i=1; i<=lines; ++i)
                    if(find(i)==find(k)) // 同一个集合(树)
                        ++ans;
                cout << ans << endl;
            }
        }
        if(T) cout << endl; // 除了最后一组每组数据后空一行
    }
    return 0;
}