다각형과 선분이 주어졌을때 저기 빨간 굵은선 처럼 저 선분의 길이의 합을 구하는건데 ( 선분 개수 max 10만)
일단 교점들의 집합들을 구하는것 까진 구현했는데 그 교점들을 갖고 다각형 내부인지 외부인지 판별하는 방법이 뭐가 있을까
먼저 생각한 아이디어는 구한 교점들을 정렬하고 나서
(0번점, 1번점) ~ (n-2 , n-1번) 점의 중간값 (x,y) 를 구하고 이 점과 다각형의 내부, 외부 판별을 하려 했더니 선분개수가 10만이여서 시간이 터질것 같단 말이야....
저 뻘건선분이 다각형을 관통할때마다 다각형 내부외부 여부가 바뀌는거라고 생각하면...?
아님 말고
그 관통의 여부를 어떻게 잡아야 할지 모르겠음 특히나 저 그림처럼 스치는 경우가 많을때처럼 말이야 맨 처음 생각한게 만들어진 교점들이 관통이 된다 -> 안된다 ->된다 -> 안된다 로 하려했는데 저 그림을 그리면서 무산이 되었더라
교점의 왼쪽 오른쪽 보고 왼쪽에서 선분이 위고 오른쪽에서 다각형이 위면 관통하는 시작점 반대면 밖으로 나오는 시작점으로 보면 안대나여 (본인 씹 프린이임)
교점이 아닌 교점이 속한 선분을 잇는 다각형의 두 점을 기준으로 보는 게 어떨까 그럼 convex 성질에 따라 관통하는 교점이 있으면 반드시 연속된 세 점이 주어지고 중간점을 포함하는 쪽이 내부니까
평행한 선이랑은 교점을 세지 말고 빨간선을 저기서 아주약간 올렸을때 교점을 구하고 아주약간 내렸을때 교점을 구해서 양쪽에 다 나타나는 점만 세면 교점 만날때마다 내외부 바뀌게 할 수 있을듯