정다각형의 모든 꼭짓점을 지나는 원은 유일하다. 가능한 모든 정n각형에 대해, 이 정다각형의 점들에 입력으로 주어진 점이 존재하는지를 확인하면 된다.
도둑은 일자로 이동하는 것이 최선이다. 경찰이 무조건 이기는 경우라면, 만약 도둑이 방향을 틀어도 경찰도 이를 따라 이동하여 도둑을 막을 수 있다. 즉, 좌표 (-INF, 0), (INF, 0), (0, -INF), (0, INF)를 기준으로 잡고 4가지 경우 각각 맨해튼 거리를 비교해주면 된다. 도둑이 경찰보다 먼저 도달할 수 있다면 도둑이 이긴다.
아이디어가 너무 좋다. 문제에서 주어진 매우 중요한 조건은 네 점이 원주에 존재하는 경우는 없다는 것이다. 삼각형을 고정하는 방법 대신, 네 점을 고정하여 사각형으로 생각해보자.
볼록 사각형의 경우, 세 점을 골랐을 때 나머지 한 점이 외접원 내에 들어오는 경우는 2가지가 존재한다.
오목 사각형의 경우에는 1가지가 존재한다.
볼록 사각형의 개수를 a, 오목 사각형의 개수를 b라고 하면, 우리가 원하는 답은 \(\frac{2a+b}{_{n}C_{3}} + 3\)이 된다. 일단, 만들 수 있는 모든 사각형의 개수는 \(_{n}C_{4}\)이므로, \(a + b=_{n}C_{4}\)이다.
한 점을 고정했을 때, 나머지 세 점을 나머지 반평면에 몰아넣을 수 있는지를 생각해보자. 이러한 경우는 볼록 다각형에서는 4가지, 오목 다각형에서는 3가지가 존재한다. 이것으로 \(4a+3b\)를 구할 수 있다. 한 점을 기준점으로 잡은 후 360도로 정렬하고, 투 포인터로 밀어주며 진행하면 된다. 전체 시간복잡도는 \(O(N^2lgN)\)이다.
(a, b) -> (2a, 2b)로 만들면, 두 수의 차는 두배가 된다. 즉 (d - c)와 (b - a)가 같아질 때까지만 두배로 만들 수 있다. 그리고 +1은 아무때나 할 수 있는데, 당연하게도 +1을 먼저 하고 2배로 올려야 a를 더 크게크게 올릴 수 있다. (+1을 시행해야 하는 횟수에서 2^k (k는 2배로 만든 횟수)를 빼주고, 이진수로 바꿔서 켜진 비트의 수를 더해주면 된다.)
BOJ 18596 - Monster Hunter (D1)
어떤 최적해가 존재한다면, 그 최적해가 속하는 정점의 부모 정점을 방문했다면 바로 이 정점으로 내려오는 것이 이득이다. union-find로 합쳐주면서 답을 루트 정점에 넣어두면 된다.
a <= b인 정점을 먼저 방문하는 것이 당연히 이득이다. 이 경우에는, a가 작은 정점부터 방문해야 한다.
a > b인 경우에는, b가 큰 정점부터 방문하는 것이 이득이다.
우선순위 큐로 최적 정점을 뽑아주면서 계산하면 된다.
BOJ 16700 - Shooter Island (P3)
유니온 파인드를 하나 더 관리해서, 어떤 점에서 최대로 오른쪽으로 갈 수 있는 점을 저장해두면 된다. 그러면 무지성(?) 유니온 파인드가 가능해진다.
'백준 문제풀이' 카테고리의 다른 글
| 백준 18619 - Alakazam (0) | 2022.10.29 |
|---|---|
| 백준 18032 - Dazzling Stars (0) | 2022.10.17 |
| 9/19 ~ 9/25 PS (0) | 2022.09.26 |
| 9/12 ~ 9/18 PS (+ 앳코더 민트) (0) | 2022.09.19 |
| 9/5 ~ 9/11 PS (0) | 2022.09.11 |