※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※
이번에 볼 문제는 백준 3688번 문제인 래프팅 디자인이다.
문제는 아래 링크를 확인하자.
https://www.acmicpc.net/problem/3688
주어지는 다각형이 볼록다각형이 아닐 수 있음에 유의하자.
내부 다각형과 외부 다각형 사이의 최단거리를 구하면 문제를 해결할 수 있을 것이다. 이 값을 어떻게 구할 수 있을까?
다각형은 선분의 집합으로 나타낼 수 있으므로, 구하고자 하는 값은 "내부 다각형을 구성하는 선분 집합"의 원소와 "외부 다각형을 구성하는 선분 집합"의 원소 사이의 최솟값으로 생각할 수 있다. 여기에서 실제로는 튜브가 동시에 접하지 못할 두 선분쌍도 골라질 수 있지만, 그러한 선분쌍의 경우 튜브가 더 작아야하게끔 하는 다각형을 구성하는 다른 선분이 존재함을 생각하면 위의 계산으로 답을 얻을 수 있다는 사실이 변하지 않는다는 점을 알 수 있다.
가능한 모든 내부 다각형의 선분과 외부 다각형의 선분의 쌍에 대하여 두 선분 사이의 거리의 최솟값들 중 가장 작은 값을 구해 문제를 해결하자.
아래는 제출한 소스코드이다.
#include <iostream>
#include <cmath>
using namespace std;
typedef long double ld;
ld func(ld X1, ld Y1, ld X2, ld Y2, ld X3, ld Y3, ld X4, ld Y4) {
ld ret = 1000000007;
ret = min(ret, hypotl(X1 - X3, Y1 - Y3));
ret = min(ret, hypotl(X1 - X4, Y1 - Y4));
ret = min(ret, hypotl(X2 - X3, Y2 - Y3));
ret = min(ret, hypotl(X2 - X4, Y2 - Y4));
ld P1, P2, Q1, Q2, R1, R2, P, Q, R;
P1 = X3, P2 = Y3, Q1 = X1, Q2 = Y1, R1 = X2, R2 = Y2;
P = (Q1 - R1) * (Q1 - R1) + (Q2 - R2) * (Q2 - R2);
Q = (P1 - R1) * (P1 - R1) + (P2 - R2) * (P2 - R2);
R = (P1 - Q1) * (P1 - Q1) + (P2 - Q2) * (P2 - Q2);
if (Q < P + R && R < P + Q) {
ld A = P1 * Q2 + Q1 * R2 + R1 * P2 - P2 * Q1 - Q2 * R1 - R2 * P1;
ld val = abs(A / sqrtl(P));
ret = min(ret, val);
}
P1 = X4, P2 = Y4, Q1 = X1, Q2 = Y1, R1 = X2, R2 = Y2;
P = (Q1 - R1) * (Q1 - R1) + (Q2 - R2) * (Q2 - R2);
Q = (P1 - R1) * (P1 - R1) + (P2 - R2) * (P2 - R2);
R = (P1 - Q1) * (P1 - Q1) + (P2 - Q2) * (P2 - Q2);
if (Q < P + R && R < P + Q) {
ld A = P1 * Q2 + Q1 * R2 + R1 * P2 - P2 * Q1 - Q2 * R1 - R2 * P1;
ld val = abs(A / sqrtl(P));
ret = min(ret, val);
}
P1 = X1, P2 = Y1, Q1 = X3, Q2 = Y3, R1 = X4, R2 = Y4;
P = (Q1 - R1) * (Q1 - R1) + (Q2 - R2) * (Q2 - R2);
Q = (P1 - R1) * (P1 - R1) + (P2 - R2) * (P2 - R2);
R = (P1 - Q1) * (P1 - Q1) + (P2 - Q2) * (P2 - Q2);
if (Q < P + R && R < P + Q) {
ld A = P1 * Q2 + Q1 * R2 + R1 * P2 - P2 * Q1 - Q2 * R1 - R2 * P1;
ld val = abs(A / sqrtl(P));
ret = min(ret, val);
}
P1 = X2, P2 = Y2, Q1 = X3, Q2 = Y3, R1 = X4, R2 = Y4;
P = (Q1 - R1) * (Q1 - R1) + (Q2 - R2) * (Q2 - R2);
Q = (P1 - R1) * (P1 - R1) + (P2 - R2) * (P2 - R2);
R = (P1 - Q1) * (P1 - Q1) + (P2 - Q2) * (P2 - Q2);
if (Q < P + R && R < P + Q) {
ld A = P1 * Q2 + Q1 * R2 + R1 * P2 - P2 * Q1 - Q2 * R1 - R2 * P1;
ld val = abs(A / sqrtl(P));
ret = min(ret, val);
}
return ret;
}
int N, M;
ld A[101][2], B[101][2];
void solve() {
ld ans = 1000000007;
cin >> N;
for (int i = 0; i < N; i++) cin >> A[i][0] >> A[i][1];
A[N][0] = A[0][0], A[N][1] = A[0][1];
cin >> M;
for (int i = 0; i < M; i++) cin >> B[i][0] >> B[i][1];
B[M][0] = B[0][0], B[M][1] = B[0][1];
for (int i = 0; i < N; i++) {
ld X1 = A[i][0], Y1 = A[i][1], X2 = A[i + 1][0], Y2 = A[i + 1][1];
for (int j = 0; j < M; j++) {
ld X3 = B[j][0], Y3 = B[j][1], X4 = B[j + 1][0], Y4 = B[j + 1][1];
ans = min(ans, func(X1, Y1, X2, Y2, X3, Y3, X4, Y4));
}
}
cout << ans / 2 << '\n';
}
int T;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout << fixed;
cout.precision(10);
cin >> T;
while (T--) solve();
}
랜덤 마라톤 (Beta) · 코스 3 H번