2개의 댓글이 있습니다.
-
-
Taeyoon_Lee -
우선 코드에 제 강의의 흔적이 보여서 뿌듯하군요. :D
어쨌든.. 우선 방법 자체를 생각해보면, 모든 선분을 볼 수 있는 영역을 구하셨다면, 그런 영역이 존재하는 순간 Yes가 될 것이고, 영역이 존재하지 않으면 No입니다. 그러니까 영역을 구하셨다면, 그 이후에는 별다른 처리가 필요하지 않은 거죠. 제 방법을 설명하자면, 입력으로 주어진 모든 선분을 직선으로 만들고, 그 n개의 직선으로 만들어지는 모든 교점 n*(n-1)/2 개를 후보로 삼아서, 모든 선분을 볼 수 있느냐를 검사했습니다. 선분을 볼 수 있냐는 선분 교차로 할 수도 있지만, 사실 이거보다 각도를 이용해서 검사하는 게 편합니다. 다만 colinear한 선분이 문제가 되는데, 이 경우를 잘 고려해주면 AC를 받아낼 수 있을 겁니다. :D
13년 전 link
-
-
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
로제폰
앞의 글 힌트대로 일단 모든 점을 볼 수 있는 영역을 찾은 후에 영역을 이루는 점들에 대해서 모든 점들을 볼 수 있는지를 체크했습니다. 샘플이랑 몇 개 예제 만든 건 잘 되는데 WA가 뜨네요.
이런 건 처음 짜보는거라 알고리즘이 잘못되었을 거 같은데 도움 부탁드립니다. 대충 설명하자면 밖에 큰 사각형을 만들고 각 선분에서 폴리곤 안쪽을 향하는 방향쪽으로 사각형을 잘라가면서 영역을 계속 업데이트 하는 방식으로 구했습니다. 끝난 뒤엔 만들어진 영역 각 점에서 폴리곤 각 점으로 선을 그을 때 크로스되는지를 체크했습니다. 아래가 소스입니다.
13년 전