백준 11563번 연돌이와 고잠녀

문제

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

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

문제풀이

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

(1) 생각

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

(2) 코드 78~86

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

(3) 코드 33~64

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

(4) 코드 48~52

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

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

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