InTheBloodHorse

每日一题(44) hud 1558线段相交

字数统计: 431阅读时长: 2 min
2019/01/06 Share

题目地址

题意

给N条线段,给一个K,问与第K条线段’相交’的线段有几条(线段之间有联系,即A与B相交,B与C相交,那么A与C也算’相交’)

思路

并查集,还是用int数组去记录关系,一个数组存index,一个数组存结果(即index位相交的线段个数)
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
#include<bits/stdc++.h>
using namespace std;

struct node{
double x,y;
}pl[1005],pr[1005];


int a[1005];
int ans[1005];

double mul(node a,node c,node b){
return (c.x-a.x)*(b.y-a.y)-(b.x-a.x)*(c.y-a.y);
}

int judge(node a,node b,node c,node d){
if(min(a.x,b.x)>max(c.x,d.x)) return false;
if(min(a.y,b.y)>max(c.y,d.y)) return false;
if(max(a.x,b.x)<min(c.x,d.x)) return false;
if(max(a.y,b.y)<min(c.y,d.y)) return false;
if(mul(a,c,b)*mul(a,b,d)<0) return false;
if(mul(c,a,d)*mul(c,d,b)<0) return false;
return true;
}

int find(int x){
int ans = x;
while(a[ans]!=-1){
ans = a[ans];
}
return ans;
}

void merge(int x,int y){
int father_x = find(x);
int father_y = find(y);
if(father_x != father_y){
a[father_y] = father_x;
ans[father_x] += ans[father_y];
ans[father_y] = 0;
}
}
int main()
{
int t;
cin >> t;
while(t--){
int n;
char tt;
int query;
cin >> n;
for(int i=0;i<=n;i++){
a[i]=-1;
ans[i]=1;
}
int index=1;
for(int i=0;i<n;i++){
cin >> tt;
if(tt=='P'){
cin >> pl[index].x >> pl[index].y >> pr[index].x >> pr[index].y;
for(int j=1;j<index;j++){
if(judge(pl[index],pr[index],pl[j],pr[j])){
merge(index,j);
}
}
index++;
}else{
cin >> query;
cout << ans[find(query)] << endl;
}
}
if(t!=0){
cout << endl;
}
}
}

CATALOG
  1. 1. 题意
  2. 2. 思路