다이아 스트릭 (1)
2달전, 입학하고 한달이 지난 4월, 슬슬 새로운 생활에도 적응하고 많은 사람들과도 알게 되었다. 그리고 뒤쳐지면 안된다는 생각에 시작했던 다이아 스트릭.. 덕분에 3주간 폐인같은 생활을 보냈다. 21일간 기하문제로 다이아 스트릭을 이었고 하루종일 문제 생각만 하면서 지냈다. 그 3주간 풀었던 문제들을 한주씩 정리해보려한다. ※ 풀이 스포 주의 4/20) 3800번 [Art Gallery] 반평면 교집합 기초문제다. 이때까지는 다이아 스트릭을 할 생각도 없었다. 4/21) 22619번 [Voronoi Island] , 1288번 [전쟁 - 국지전] 각 점에서 다른 점까지 수직이등분선을 경계로 하는 반평면들의 교집합을 구하는 방법으로 naive하게 보로노이 다이어그램을 구할 수 있었다. 4/22) 23194번 [Domes] 두 점을 지나는 직선을 지나면 두 점의 순서가 바뀌는것을 관찰 후 모든 점 쌍에 대해 순서가 올바르도록 하는 반평면 범위의 교집합을 구하면 끝난다. 4/23~24) 1853번 [정사영] , 3873번 [Intersection of Two Prisms] 두 평면에 공통된 축을 기준으로 구분구적법을 이용해 잘게 쪼개 직사각형 넓이를 전부 더해서 구했다. 꼭짓점마다 구간을 나눠 적분하면 좋겠지만 귀찮아서 구분구적법을 썼는데 의외로 오차가 널널해 잘 돌아갔다. 이때부터는 스트릭을 의식하고 있었고 두 문제로 2일의 스트릭을 채웠다. 4/25) 22594번 [Shelter] 보로노이 다이어그램을 구성한 후 각 구역에서 대피소까지 거리제곱의 기댓값을 구하면 되는 문제다. 대피소를 기준으로 다각형을 삼각형으로 쪼개 구하려 했다. 결국 이렇게 삼각 분할을 하여도 미적분 지식 없이 풀지 못한다.. 하지만 위 문제에서 하루의 시간을 더 끈 덕분에 조금 더 생각할 시간이 많았고, 직접 시뮬레이션 돌릴 값을 바탕으로 두 변과 사이각의 각도로 표현 되는 일반항을 찾기 시작했다. 그렇게 생각할 수 있는 모든 형태에서 계수를 비교하...