rotating calipers 썸네일형 리스트형 SCPC 2017 본선 2번 풀이. Bridge 문제 설명(요약)평면 위에 볼록다각형 모양의 두 섬 A와 B가 있다. A와 B는 서로 교차하지 않는다. A와 B 사이에 다리를 놓으려고 하는데, 다리 건설 비용을 최소화하기 위해 다리의 길이를 최소화하려고 한다.다리의 A쪽 끝점 P와 B쪽 끝점 Q에 대해, P는 A의 내부나 경계에, Q는 B나 내부의 경계에 위치해야 한다.다리(선분 PQ)의 길이를 최소화하는 점 P와 Q에 대해, 그 길이를 구하여라.제약 조건: A, B의 꼭짓점 수 N, M은 각각 200,000 이하* 부분문제 1 (82점): N, M 더보기 이전 1 다음