[BOJ 3688 // C++] 래프팅 디자인

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 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번