HDOJ 1558 [并查集][线段相交]

题目

Segment Set

题意

给你一些操作,输入P时,后边的四个值分别代表一条线段的起点、终点坐标,

输入Q时,后边输入一个整形值K,输出第k条线段所在的集合中包含的线段的个数。

样例输入

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

题解分析

线段相交 + 并查集

每加入一条线段,就马上遍历一遍之前的所有线段,如果与之前的某条线段相交,merge一下。

输入Q之后,直接输出线段K所在集合包含的线段数量。

这里我也是才知道将merge函数这样写可以计算集合元素数量:

1
2
3
4
5
6
7
8
9
10
11
12
void merge(int x,int y)
{
int b1,b2;
b1 = getf(x);
b2 = getf(y);
if(b1!=b2)
{
son[b2] = b1;
num[b1]+=num[b2]; //该集合元素数量
}
return;
}

初始化的时候也稍微修改一下:

1
2
3
4
5
for(int i=1; i<=n; i++)
{
son[i] = i;
num[i] = 1;
}

最后注意格式!!!

There is a blank line between test cases.

意味着两组数据之间有空行!而且最后一组之后不用换行!!

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
typedef struct
{
double x,y;
} Point;
int son[1001];
int num[1001];
Point p1[1001],p2[1001];
double cal(Point a,Point b,Point c)
{
return (c.x-a.x)*(b.y-a.y)-(b.x-a.x)*(c.y-a.y);
}
int check(Point a,Point b,Point c,Point d)
{
if(min(a.x,b.x)>max(c.x,d.x)||min(c.x,d.x)>max(a.x,b.x)
||min(a.y,b.y)>max(c.y,d.y)||min(c.y,d.y)>max(a.y,b.y))
return 0;
//先简单筛一下,防止(0,0)(1,1)/(2,2)(3,3)这种
double d1,d2,d3,d4;
d1 = cal(a,b,c);
d2 = cal(a,b,d);
d3 = cal(c,d,a);
d4 = cal(c,d,b);
if(d1*d2<=0&&d3*d4<=0) return 1;
else return 0;
}
int getf(int x)
{
return son[x]==x?x:getf(son[x]);
}
void merge(int x,int y)
{
int b1,b2;
b1 = getf(x);
b2 = getf(y);
if(b1!=b2)
{
son[b2] = b1;
num[b1]+=num[b2]; //该集合元素数量
}
return;
}
int main(void)
{
int T;
scanf("%d",&T);
while(T--)
{
int n;
scanf("%d",&n);
for(int i=1; i<=n; i++)
{
son[i] = i;
num[i] = 1;
}
int i=1,k;
char mode;
while(n--)
{
getchar();
scanf("%c",&mode);
if(mode=='P')
{
scanf(" %lf %lf %lf %lf",&p1[i].x,&p1[i].y,&p2[i].x,&p2[i].y);
if(i>1)
{
for(int j=1; j<i; j++)
{
if(check(p1[j],p2[j],p1[i],p2[i]))
{
merge(j,i);
}
}
}
i++;
}
else if(mode=='Q')
{
scanf("%d",&k);
printf("%d\n",num[getf(k)]);
}
}
if(T) printf("\n");
}
return 0;
}