볼록껍질
-
백준 3878 점 분리 c++ (증명)카테고리 없음 2021. 8. 25. 23:43
코드는 다른 블로그에 많으니 왜 두 점 집합의 볼록포가 서로 겹치지 않으면 분리하는 직선이 있는지에 대해 증명을 하도록 하겠습니다. 일반적으로 두 볼록도형 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의 왼..