[백준 19650] 개미여행

작성일 | In |

문제 링크

https://www.acmicpc.net/problem/19650

풀이

문제를 다시 정의하자면 “볼록 껍질의 내부에 들어가지 않고 출발점에서 도착점으로 가는 최단 거리” 를 구해야 합니다. 최단 거리가 되기 위해서는 점끼리 직선으로 이어진 경로만을 따라서 가야 한다는 것은 자명합니다. 점의 개수도 최대 $102$개이므로 $N^2$의 모든 직선을 보아도 괜찮습니다. 하지만 모든 직선을 사용할 수는 없고 볼록껍질 내부를 지나지 않아야 하므로 판별을 해주어야 합니다.

경로는 볼록껍질의 한 변과 교차해서는 안됩니다. 교차를 하게되면 당연히 내부에서 외부로 혹은 외부에서 내부로 들어간다는 것이기 때문에 볼록껍질의 내부를 반드시 지나게 되므로 이 경로는 사용할 수 없습니다. 여기서 주의할 점이 교차를 판정하기 위해서는 접하는 것을 포함하지 않고 완전히 교차해야 한다는 것입니다. 접하는 것을 포함해버리면 가능한 경로인 볼록껍질의 변을 이용하는 것을 허용하지 않게 됩니다.

그리고 출발점과 도착점이 한 볼록껍질 내부에 있을 수 있습니다. 여기서 두번째로 판별해야 할 것이 있는데, 경로의 두 점중 하나라도 볼록껍질의 내부에 있으면 안됩니다. 하지만 두 점이 볼록껍질의 변 위에 있고 선분이 볼록껍질의 내부로 이어지면 판별이 되지 않습니다. 그러므로 다른 방법을 찾아야 하는데 선분의 중점이 볼록껍질 내부에 있는지 확인하면 두 점을 따로 확인할 필요 없이 그것만으로 판별을 할 수 있습니다. 점이 내부에 있는지 확인하려면 볼록껍질의 모든 변에서 점으로의 ccw를 확인해서 모든 결과가 안쪽에 있다고 나오는지 확인하면 됩니다.

여기서 끝난다면 좋겠지만 예외처리를 하나 더 해야할 것이 있습니다.

개미여행1

위 사진에 있는 빨강 경로는 1) 볼록껍질의 한변과 교차하지 않으면서 2) 경로의 중심이 볼록껍질 내부에 있지 않습니다.

그래서 제가 떠올린 풀이는 볼록껍질의 꼭짓점에 아주 작은 변을 두개 만들어 1번 판정을 이용하는 것입니다.

개미여행2

위 사진처럼 아주 작은 선분을 꼭짓점마다 있다고 생각하고 판정에 이용하여 꼭짓점을 통해 통과하는 것을 막았습니다. 하지만 저 작은 선분이 경로와 평행한다면 제대로 찾을 수 없기 때문에 문제가 될 수도 있겠지만 꼭지점마다 x축에 평행하게 한번 y축에 평행하게 한번 확인하여 문제를 해결하였습니다.

이렇게 가능한 모든 경로를 찾게 된다면 그 경로를 이용해 최단 거리를 찾는 알고리즘(플로이드 와샬 $O(N^3)$, 다익스트라 $O(N^2\log N)$)로 정답을 구할 수 있습니다.

전체 코드

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
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
include<bits/stdc++.h>
using namespace std;
using ll = long long;

struct point{
	double x, y;
	bool operator < (const point &a)const{
		return tie(x,y) < tie(a.x,a.y);
	}
	point operator - (const point &a)const{
		return {x-a.x, y-a.y};
	}
	bool operator == (const point &a)const{
		return tie(x, y) == tie(a.x, a.y);
	}
}s, e;
int n, chk[333];
vector<int> v[333];
vector<point> in[333], st[333], l;
priority_queue<pair<double, int>> pq;

ll cross(point a, point b){
	return a.x * b.y - a.y * b.x;
}

double dist(point a, point b){
	return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}

int ccw(double a,double b,double c,double d,double e,double f){
	c-=a, e-=a;
	d-=b, f-=b;
	double cross = c*f - d*e;
	if(cross > 0) return 1;
	if(cross < 0) return -1;
	return 0;
}

bool f(int A, int B){
	point a = l[A], b = l[B];
	point c = {(a.x + b.x)/2, (a.y + b.y)/2};

	for(int i=1;i<=n;i++){
		int fl = 1;
		for(int j=0;j<st[i].size() && fl;j++){
			point k = st[i][(j+1)%st[i].size()];
			if(ccw(st[i][j].x, st[i][j].y, k.x, k.y, c.x, c.y) <= 0) fl = 0;
		}
		if(fl) return false;
	}

	for(int i=1;i<=n;i++){
		for(int j=0;j<st[i].size();j++){
			point C = st[i][j], D = st[i][(j+1)%st[i].size()];
			int AA = ccw(C.x, C.y, D.x, D.y, a.x, a.y) * ccw(C.x, C.y, D.x, D.y, b.x, b.y);
			int CC = ccw(a.x,a.y,b.x,b.y,C.x,C.y) * ccw(a.x,a.y,b.x,b.y,D.x,D.y);
			if(AA<0 && CC<0) return false;
		}
	}

	for(int i=1;i<=n;i++){
		for(int j=0;j<st[i].size();j++){
			point C = st[i][j], D = st[i][j];
			C.x -= 1e-1, D.x += 1e-1;
			int AA = ccw(C.x, C.y, D.x, D.y, a.x, a.y) * ccw(C.x, C.y, D.x, D.y, b.x, b.y);
			int CC = ccw(a.x,a.y,b.x,b.y,C.x,C.y) * ccw(a.x,a.y,b.x,b.y,D.x,D.y);
			if(AA<0 && CC<0) return false;
		}
	}

	for(int i=1;i<=n;i++){
		for(int j=0;j<st[i].size();j++){
			point C = st[i][j], D = st[i][j];
			C.y -= 1e-1, D.y += 1e-1;
			int AA = ccw(C.x, C.y, D.x, D.y, a.x, a.y) * ccw(C.x, C.y, D.x, D.y, b.x, b.y);
			int CC = ccw(a.x,a.y,b.x,b.y,C.x,C.y) * ccw(a.x,a.y,b.x,b.y,D.x,D.y);
			if(AA<0 && CC<0) return false;
		}
	}

	return true;
}

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin >> s.x >> s.y >> e.x >> e.y;
	cin >> n;
	for(int i=1;i<=n;i++){
		int a; cin >> a;
		while(a--){
			double x, y; cin >> x >> y;
			in[i].push_back({x, y});
		}

		if(in[i].size() <= 2){
			in[i].clear();
			i--, n--;
			continue;
		}

		int it = min_element(in[i].begin(), in[i].end()) - in[i].begin();
		swap(in[i][0], in[i][it]);
		sort(in[i].begin()+1, in[i].end(), [&](point &a, point &b){
			ll re = cross(a - in[i][0], b - in[i][0]);
			return re ? re > 0 : a < b;
		});

		for(int j=0;j<in[i].size();j++){
			while(st[i].size() >= 2 && cross(st[i][st[i].size()-1]-st[i][st[i].size()-2], in[i][j]-st[i][st[i].size()-2]) <= 0) st[i].pop_back();
			st[i].push_back(in[i][j]);
		}
	}


	l.push_back(s);
	l.push_back(e);
	for(int i=1;i<=n;i++) for(auto k : st[i]) l.push_back(k);

	for(int i=0;i<l.size();i++) for(int j=i+1;j<l.size();j++) if(f(i, j)) v[i].push_back(j), v[j].push_back(i);

	pq.push({0, 0});
	while(!pq.empty()){
		int u = pq.top().second;
		double c = -pq.top().first;
		pq.pop();

		if(u == 1){
			cout << fixed << setprecision(12) << c;
			return 0;
		}

		if(chk[u]) continue;
		chk[u] = 1;

		for(auto x : v[u]) if(!chk[x]) pq.push({-c -dist(l[u], l[x]), x});
	}

	cout << -1;
}

여담

볼록껍질을 구해야 한다는 점 외에는 2125. 좀과 동일한 문제입니다 (입력 형식만 고친다면 AC를 받을 수 있습니다). solved.ac 경험치 냠냠!