다이아 스트릭 (2)

3주간의 다이아 스트릭중 둘째주에 푼 문제들을 정리해봤다.

※ 풀이 스포 주의

4/27) 3527번 [Jungle Outpost]

문제에서 엄격하게 내부에 존재해야 한다는 조건이 있어 특별한 예외처리 없이 연속된 탑을 폭파했을때 반평면 교집합의 존재여부로 이분 탐색을 하면 된다.

4/28) 3906번 [How I Mathematician Wonder What You Are!]

공선점이 없다는 조건 덕분에 이 문제도 예외처리 없이 반평면 교집합의 존재 여부만 구해주면 된다.

4/29) 9212번 [트라이앵글]

첫번째 삼각형을 포함하는 평면을 기준으로 두번째 삼각형의 세 변과 교점을 구한후 교점이 첫번째 삼각형의 내부,외부 둘다 존재한다면 꼬여있음을 알 수 있다.

4/30) 27861번 [Linked Triangles]

6개의 점을 두 삼각형으로 분할하는 모든 경우를 위 문제와 같은 방법으로 해보면 된다.

문제를 푸는것과는 별개로 일반적인 위치에서 이러한 분할이 항상 존재한다는 사실은 재밌었다.

5/1) 17441번 [파리채 만들기]

이전 글에서 Shelter(22594번)을 풀며 삼각형의 한 꼭짓점과 내부 임의의 점까지 거리 제곱의 기댓값을 구하는 방법을 알아냈다. 이번에는 다각형 내부에서 두 점 사이 거리 제곱의 기댓값이다.

미적분학 베이스가 없어 그린정리는 커녕 적분 식 조차 세우지 못하기 때문에 다른 관점으로 생각을 해야했다. 처음 접근은 다각형 내 무게중심과 한 점 사이 거리 제곱 기댓값이 두 점 사이 거리 제곱 기댓값과 동일할 것이라고 직관으로 찍어봤다. 다각형의 무게중심을 구한뒤 삼각형으로 분할해 지난번에 얻은 식을 쓸 수 있었다. 그렇게 구한 값은 원하던 답은 아니였지만 몬테카를로로 구해본 값과 비교했을때 항상 절반으로 나타났고 그대로 두배한값을 내는 코드를 제출해 PBA를 했다.

5/2) 14633번 [Airport Construction]

꽤나 고생을 한 문제다. 두 점을 선택해 만들 수 있는 직선 위 선분중 하나가 최대인 것을 확인하고 모든 직선에 대해 만나는 변을 방향과 함께 기록하며 풀어 보려 했으나 실패했다. 교점과 만나는 방향을 함께 처리하는 방법이 오히려 안전하다고 생각했는데 고쳐도 끝이 없는 반례들을 보고 오히려 처음에 안전하지 못하다고 생각했던 교점만 기록하는 방법으로 짜봤고, 반례를 생각할 필요도 없이 한번에 통과했다...

구현 자체는 다각형을 돌면서 최대 연속한 세 변을 보는 방법으로 간단하게 구현할 수 있었다.

5/3) 11860번 [Squares]

여러 정사각형들의 총 넓이를 구해주는 문제로 포함배제를 이용하면 된다. 사각형들의 교집합을 구해줄때 모든 교차점을 찍고 내부의 점에 대해 볼록껍질을 만들면 되는 것 같은데 그냥 hpi로 풀었다.