백준 3878 점 분리 c++ (증명)

 코드는 다른 블로그에 많으니 왜 두 점 집합의 볼록포가 서로 겹치지 않으면 분리하는 직선이 있는지에 대해 증명을 하도록 하겠습니다. 

 

 일반적으로 두 볼록도형 A,B가 서로 겹치지 않을 때 ( 교집합이 없을 때) 어떤 직선이 있어 두 도형을 분리시킴을 보입시다. A에 속하는 점 P와 B에 속하는 점 Q중 PQ의 거리가 가장 짧은 P와 Q를 선택해줍시다. 그리고 P와 Q를 의 수직 이등분선 l을 생각해줍시다. 이제 l이 조건을 만족함을 보입시다.

 

 먼저 P, Q는 각각 A와 B의 경계에 있습니다. 증명은 PQ 선분과 A와 B의 경계사이 교점을 잡아주면 최소성으로 증명할 수 있습니다.

 

 이제 P를 지나며 l에 평행한 직선 lP 를 생각해줍시다. lP는 A와 경계에서만 만납니다. 정확히 말하면 P를 기준으로 A의 왼쪽 경계와 오른쪽 경계가 각각 lP에 대해 각각 시계방향, 반시계방향으로 휘어있어야 하는데 안그러면 P를 미소거리만큼 움직여주면 최소성이 깨지게 됩니다. (적당히 코사인 제2 법칙 써주면 됩니다.) 그래서 l은 A와 안만남을 알 수 있습니다. 마찬가지로 l은 B와도 안만나고 따라서 l이 조건을 만족함을 알 수 있습니다.