tobey2j0   1년 전

제가 아래 코드와 같이 그냥 대영이, 영훈이, 범준이의 좌표에서 다각형 밖의 점에다가 선을 그어서 교점 개수 확인해 주는 식으로 풀었는데, 이런 식으로 풀어도 되는 건가요?

이런 식으로 풀어도 되면 Platinum IV까지의 난이도는 아닌 것 같은데..

zenith82114   1년 전

난이도가 왜 높은지 모르겠을 때에는 증명을 해보면 좋습니다.

kwakws0627   1년 전

문제 태그 보시면은 이 문제는 오목 다각형 내부 점 판정 법을 알고 있어야 풀 수 있습니다.

구현 자체는 간단하지만 ccw, 선분 교차 판정 및 질문자분께서 말한 

"~의 좌표에서 다각형 밖의 점에다가 선을 그어서 교점 개수 확인해 주는 식" 의 정당함을 증명하는게 쉽지는 않아서

솔브닥 난이도가 높게 평가된 거 같습니다.

 

그리고 아래 반례 한 번 확인해주세요.

답이 어떻게 나와야 되는지요.

tobey2j0   1년 전

저도 제 풀이가 완벽하지 않다는 것은 알고 있습니다.

하지만 아래 제가 제출한 코드를 보면 알 수 있듯이 저는 저 코드를 통해 AC를 받았습니다.

https://www.acmicpc.net/source...

아래 문제(30924번: A+B - 10)을 보면 100% 맞는 코드가 아닌데도 정답 처리를 해 주는 것을 볼 수 있는데, 이것도 그와 마찬가지로 생각할 수 있는 것 아닌가요?

https://www.acmicpc.net/proble...

kwakws0627   1년 전

r1, r2를 랜덤으로 잡아서 풀어도 AC 받네요.

질문자분 말씀처럼 30924 문제처럼 무작위화로 풀 수 있다고 생각하셔도 될 거 같네요.

 

추가로, 구글에 검색하거나 아니면 gpt에게 물어봐서 "ray casting 알고리즘" 에 대해 찾아보세요.

간략히 말하면, 다각형 내 점에서 수평 (또는 수직)으로 굉장히 긴 직선을 긋고,

이 직선과 몇 개의 다각형 선분들과 교차하는지, 그 홀짝으로 내부의 점인지 판단하는 알고리즘 입니다.

 

레이 캐스팅 알고리즘에서 복잡한 부분이 있는데요,

긴 직선과 다각형의 선분이 겹치거나, 혹은 두 선분의 교점이 다각형의 꼭지점일 때 처리가 꽤나 머리 아픕니다. (생각해보니 겹칠 때는 크게 문제되지 않네요)

(이 문제 질문글들 대부분이 이 예외처리 관련 질문 혹은 이 때 예외처리 잘못된 코드 저격 데이터입니다.)

이 때 어떻게 처리하면 되는지 질문자분께서 스스로 한 번 생각해보세요.

아마도 이 예외처리 때문에 솔브닥 난이도가 더 높아졌다고 생각해도 될 거 같아요.

댓글을 작성하려면 로그인해야 합니다.