백준 4995 - 원과 점 (Python)

문제 정보

• https://www.acmicpc.net/problem/4995
• 기하학, 브루트포스

---

문제 정리

아래 사진처럼 2차원 평면 위에 N개의 점이 있을 때, 반지름이 1인 원으로 점을 최대 몇 개까지 포함시킬 수 있는지 구하는 문제이다.

---

풀이

• 한 가지 관찰을 할 수 있다.
  최적해는 어떤 원의 원주 위에 두 점이 위치하는 경우 중에 반드시 존재한다.

• 브루트포스로 두 점이 원주 위에 존재하는 상황을 전부 탐색해보자.
  두 점 사이의 거리가 2r 이하인 경우만 탐색하면 된다.
  여기에서 O(N^2)의 시간이 걸린다.

• 거리가 2r 이하인 두 점이 도출되었으면, 이제 두 점을 원주 위에 두도록 하는 원의 중심 좌표를 찾아야 한다.
  이런 원은 총 2개가 존재하며, 두 점의 거리가 2r인 경우에는 1개만 존재한다.

• 어케어케 잘 수식을 정리해서 원의 중심 좌표를 구했으면 이제 이 원 내부에 존재하는 점의 개수를 세주면 된다.
  모든 점에 대해 원의 중심 점과의 거리가 r 이하인 점의 개수를 세는 방식으로 O(N)의 시간이 걸린다.

• 이 과정을 전부 처리하면 O(N^3)에 문제를 해결할 수 있다.

• 위 과정을 계산할 때, 실수 오차를 주의해야 한다.
  또한, 두 점 사이의 거리가 2r 이하인 경우가 존재하지 않을 경우에는 0이 아니라 1을 출력해야 한다.

---

후기

개수 체크를 0개로 했다가 10%틀했다.
그리고 테케가 생각보다 많은듯?

---

코드

# 백준 4995

import io
from math import sqrt

input = io.BufferedReader(io.FileIO(0), 1<<18).readline
r = 1
EPS = 1e-12


def solve(N, points):
    maxCount = 1
    for i in range(N-1):
        for j in range(i+1, N):
            # i번 점, j번 점이 원주 위에 있도록 원의 중심 좌표 구하기
            dx = points[j][0]-points[i][0]
            dy = points[j][1]-points[i][1]
            d2 = dx*dx + dy*dy
            if d2 > 4*r*r + EPS:
                continue
            d = sqrt(d2)
            mX = (points[i][0] + points[j][0]) / 2
            mY = (points[i][1] + points[j][1]) / 2
            h = sqrt(max(0, r*r - d2/4))

            circle = [(mX - dy*h/d, mY + dx*h/d), (mX + dy*h/d, mY - dx*h/d)]

            # (cX, cY)가 중심 좌표일 때, 해당 원 내부에 존재하는 점의 개수 체크
            for cX, cY in circle:
                count = 0
                for k in range(N):
                    if (points[k][0]-cX)**2 + (points[k][1]-cY)**2 <= r*r + EPS:
                        count += 1

                maxCount = max(maxCount, count)

    return maxCount


def main():
    while True:
        N = int(input())
        if N == 0:
            break
        points = []
        for _ in range(N):
            points.append(list(map(float, input().split())))

        print(solve(N, points))


main()