首页 > ACM题库 > HDU-杭电 > HDU 1558 Segment set-并查集-[解题报告] C++
2013
12-12

HDU 1558 Segment set-并查集-[解题报告] C++

Segment set

问题描述 :

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.

输入:

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.

输出:

For each Q-command, output the answer. There is a blank line between test cases.

样例输入:

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

点击打开hdu 1558

思路: 计算几何+并查集
分析:
1 有n个操作,最后求有几个集合或者说是连通分量
2 对于输入一条线段我们就去前面找能够和它相交的线段,利用并查集进行合并并且更新rank数组,rank[x]数组保存的是以x为跟节点的集合的线段的数量
3 这一题难点就是线段的相交判断

代码:

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const double eps = 1e-8;
const double INF = 1<<30;
const int MAXN = 1010;

struct Node{
    double x1;
    double y1;
    double x2;
    double y2;
};
Node node[MAXN];

int n;
int father[MAXN];
int rank[MAXN];

void init(int m){
    for(int i = 0 ; i <= m ; i++){
        father[i] = i;
        rank[i] = 1;
    }
}

int find(int x){
    if(father[x] != x){
        int fa = father[x];
        father[x] = find(fa);
        rank[x] += rank[fa];
    }
    return father[x];
}

double multiply1(Node a , Node b){
    return (a.x1-a.x2)*(b.y1-a.y1)-(a.y1-a.y2)*(b.x1-a.x1);
}

double multiply2(Node a , Node b){
    return (a.x1-a.x2)*(b.y2-a.y1)-(a.y1-a.y2)*(b.x2-a.x1);
}

bool inter(Node a , Node b){
    if(max(a.x1,a.x2) >= min(b.x1,b.x2) &&
            max(b.x1,b.x2) >= min(a.x1,a.x2) &&
            max(a.y1,a.y2) >= min(b.y1,b.y2) &&
            max(b.y1,b.y2) >= min(a.y1,a.y2) &&
            multiply1(a,b) * multiply2(a,b) <= eps &&
            multiply1(b,a) * multiply2(b,a) <= eps)
        return true;
    else return false;
}
void solve(){
    for(int i = 1 ; i < n ; i++){
        if(inter(node[i] , node[n])){
            int fx = find(i); 
            int fy = find(n);
            if(fx != fy){
                father[fy] = fx;
                rank[fx] += rank[fy];
            }
        }          
    }
}

int main(){
    int cas , m , k;
    bool isFirst = true;
    char c;
    scanf("%d" , &cas);
    while(cas--){
        if(isFirst)
            isFirst = false;
        else
            puts("");
        n = 1;
        scanf("%d%*c" , &m); 
        init(m);
        while(m--){
            c = getchar(); 
            if(c == 'P'){
                scanf("%lf" ,&node[n].x1);       
                scanf("%lf" ,&node[n].y1);       
                scanf("%lf" ,&node[n].x2);       
                scanf("%lf%*c" ,&node[n].y2);       
                if(node[n].x1 > node[n].x2){
                    swap(node[n].x1 , node[n].x2); 
                    swap(node[n].y1 , node[n].y2); 
                }
                solve();
                n++;
            }
            else{
                scanf("%d%*c" , &k); 
                int fa = find(k);
                printf("%d\n" , rank[fa]);
            }
        }
    }
    return 0;
}

解题报告转自:http://blog.csdn.net/chenguolinblog/article/details/9905143