이런 경우는 어떨까요?
10900번 - Lonely mdic
교차점을 모두 구하고, 호의 포함관계를 구하신 것 까지는 매우 잘 했습니다. 만 요구하는 것은 둘레가 아니라 면적을 구해서 판단해야하기 때문에 어딘가 많이 부족합니다.
doju 님이 남겨주신 반례가 해당 내용입니다.
그린정리, 스트로크 정리 등은 분명 용어는 어려워 보이지만 본질은 신발끈 공식만 찾아서 읽어봐도 거의 일맥상통하는 내용이니까 겁먹으실 필요 없습니다.
저는 적분을 해서 풀었지만 님과 비슷한 방법으로 푸신 분들이 있고, 접근 방법 자체가 틀린 것도 아닙니다.
원 a를 볼 때, 원 a의 호가 모두 다른 원들에 의해 숨어있는가에 더해서 뭔가를 더 봐준다면 굳이 적분을 하지 않아도 답을 구할 수 있는 방법이 있습니다.
조금만 더 머리를 굴려보시길 바랍니다.
doju님 redcube231님 두분 다 친절한 답변 감사드립니다ㅠ 적분을 통한 방법도 있었군요...
일단 주신 반례를 통해 좀 더 연구해보겠습니다!
댓글을 작성하려면 로그인해야 합니다.
yechandubai 1년 전 2
다이아 상위 문제를 왜 덤비냐고 하실 수도 있는데… 삼각함수 쪽은 그래도 좀 자신이 있어서 한 번 도전해보고 싶었습니다.
인터넷 뒤져가면서 도형의 불 연산 같은 것도 이것저것 공부해 보고, 나름 로직을 짜서 구현까지는 해둔 상태입니다.
원들의 교차점을 모두 구한 다음, 각 원에 대해 교차점들 사이의 호를 보고, 그 호의 중간점이 다른 원들 내부에 있으면 그 부분은 가려진 호,
하나라도 바깥에 노출된 호가 있으면 그 원은 경계를 가진다고 판단했습니다. (접접이 하나인 원이야 테두리에 영향이 없으니 생각할 필요도 없고...)
만약 교차점이 아예 없다면 둘레 위 임의의 점 하나만 찍어서, 그 점이 바깥이면 독립원, 안쪽이면 통째로 가려진 노답원이라고 보고 있습니다.
문제는 이렇게 풀어도 38%에서 자꾸 오답이라고 나오네요.
알고리즘 분류를 보니 그린 정리가 있어서 이걸 활용해야 되나 싶어서 찾아봤는데, 폐곡선이라던지 스트로크 정리라던지 모르는 용어만 잔뜩 나오고...
혹시 제가 생각치 못한 반례가 있을까요?
제네레이터까지 만들어서 랜덤 테스트 돌리고, 직접 그래프도 그려서 눈으로 비교해 봤는데, 제가 찾은 반례에서는 전부 맞게 나오더라구요.
아니면, 제가 너무 무모한 도전을 한 것일까요?
그래도 한 번 끝까지 파보고 싶어서 질문드립니다.