백준 11563번 연돌이와 고잠녀

문제

연돌이와 고잠녀는 유치원 시절부터 친한 친구였다. 하지만 한 순간의 잘못된 선택으로 인해 서로 만나기 힘들게 되었다. 신촌에서 안암으로 갈 수 없기 때문이다. 이를 딱하게 여긴 국토교통부 장관은 도로를 하나 놓아주기로 했다. 하지만 재정상의 문제로 도로의 길이는 가능한 한 짧아야 한다.

2차원 평면 위에 신촌에 연결된 직선도로들의 정보와 안암에 연결된 직선도로들의 정보가 주어진다. 연돌이는 도로 위를 통해서만 이동할 수 있고, 두 도로가 만나는 지점에서 도로를 갈아탈 수 있다. 신촌에서 안암으로 갈 수 있도록 새로 설치할 도로의 최소 길이를 알려주자.

문제풀이

사용한 알고리즘: CW-CCW (기하)

(1) 생각

 신촌 도로와 안암 도로 사이의 최소 거리를 구하는 문제입니다.
 즉, 선분과 선분 사이의 거리를 구하는 문제입니다.

(2) 코드 78~86

 신촌의 모든 도로와 안암의 모든 도로 사이의 거리 중 최소거리를 구합니다.

(3) 코드 33~64

 두 선분간의 (최소)거리는
 1. 꼭지점 간의 거리
 2. 한 선분의 꼭지점에서 다른선분에 내린 수선의 길이
 둘 중 하나입니다.

(4) 코드 48~52

 꼭지점 간 거리는 그냥 구해줍니다.

(5) 코드 16~32, 53~61

 수선길이는 내적과 외적을 이용해줍니다.
 꼭지점이 다른 선분의 위에 있어서 수선을 내릴 수 있는지 내적을 사용해 판단하고,
 수선의 길이는 외적을 사용해 구해줍니다.

	#include <bits/stdc++.h>
	using namespace std;
	int N, M;
	struct Point{
	double x1, y1, x2, y2;
	Point(){}
	Point(double a1, double b1, double a2, double b2) : x1(a1), y1(b1), x2(a2), y2(b2){}
	};
	Point A[2222];
	Point B[2222];
	// x, y 사이의 거리
	double Distance(double x1, double y1, double x2, double y2){
	return sqrt(pow(x1-x2, 2) + pow(y1-y2, 2));
	}
	// 벡터 x, y의 내적
	double dot(double x1, double y1, double x2, double y2){
	return x1*x2 + y1*y2;
	}
	// 벡터 x, y의 외적
	double cross(double x1, double y1, double x2, double y2){
	return x1*y2 - x2*y1;
	}
	// 선분 12에 점 3에서 수선의 발을 내릴 수 있으면 수선의 길이, 아니면 -1 리턴
	double perpendicular(double x1, double y1, double x2, double y2, double x3, double y3){
	double dot1 = dot(x2-x1, y2-y1, x3-x1, y3-y1);
	double dot2 = dot(x1-x2, y1-y2, x3-x2, y3-y2);
	// 점 3이 선분 12와 예각 2개를 이루면 수선을 내릴 수 있음
	if(dot1*dot2 >= 0)
	return abs(cross(x2-x1, y2-y1, x3-x1, y3-y1)) / Distance(x1, y1, x2, y2);
	return -1;
	}
	// p1 의 선분 AB 와 p2 의 선분 CD 사이거리
	double Path(Point p1, Point p2){
	// 점 A (a1, a2)
	double a1 = p1.x1;
	double a2 = p1.y1;
	// 점 B (b1, b2)
	double b1 = p1.x2;
	double b2 = p1.y2;
	// 점 C (c1, c2)
	double c1 = p2.x1;
	double c2 = p2.y1;
	// 점 D (d1, d2)
	double d1 = p2.x2;
	double d2 = p2.y2;
	// 먼저 모든 점 쌍 사이의 거리가 후보가 될 수 있음
	double dist = Distance(a1, a2, c1, c2), temp;
	dist = min(dist, Distance(a1, a2, d1, d2));
	dist = min(dist, Distance(b1, b2, c1, c2));
	dist = min(dist, Distance(b1, b2, d1, d2));
	// 어느 점에서 다른 선분에 수선을 내릴 수 있으면 수선의 길이도 후보
	temp = perpendicular(a1, a2, b1, b2, c1, c2);
	if(temp >= 0) dist = min(dist, temp);
	temp = perpendicular(a1, a2, b1, b2, d1, d2);
	if(temp >= 0) dist = min(dist, temp);
	temp = perpendicular(c1, c2, d1, d2, a1, a2);
	if(temp >= 0) dist = min(dist, temp);
	temp = perpendicular(c1, c2, d1, d2, b1, b2);
	if(temp >= 0) dist = min(dist, temp);
	return dist;
	}
	int main(){ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	cin >> N >> M;
	for (int i = 0; i < N; ++i){
	double a, b, c, d;
	cin >> a >> b >> c >> d;
	A[i] = Point(a,b,c,d);
	}
	for (int i = 0; i < M; ++i){
	double a, b, c, d;
	cin >> a >> b >> c >> d;
	B[i] = Point(a,b,c,d);
	}
	double ans = -1;
	for (int i = 0; i < N; ++i){
	for(int j = 0; j < M; ++j){
	auto p = A[i];
	auto q = B[j];
	if(ans<0) ans = Path(p,q);
	else ans = min(ans, Path(p,q));
	}
	}
	cout<<fixed;
	cout.precision(16);
	cout << ans << '\n';
	return 0;
	}

view raw BOJ 11563.cpp hosted with ❤ by GitHub