[Python]2389-세상의 중심에서...

www.acmicpc.net/problem/2389

2389번: 세상의 중심에서...

비슷한 문제 ssuallassualla.tistory.com/156

 

처음에 봤을때는 오차를 $10^{-3}$으로 매우 후하게 줘서 쉬운문제일줄 알았다.

그래서 컨벡스헐 그린다음에, 가장 먼 두점 잡고 중점해서 원 그리는 방식으로 접근했다. 당연히 틀렸다.

그래서, wethinknewrise.tistory.com/5이 블로그를 참고해서 풀었다.

어디서는 simulated annealing이라고도 하고, 경사하강법이라고도 하던데, 아직 뭘 몰라서 구분을 못하겠다.

 

문제푸는 방법이 신기하다. 뭔가 인공지능 분야에서 쓸거 같은 느낌도 든다.

지금까지 나는 한번에 정확히 뭔가를 찾아내는 알고리즘만을 배웠는데, 점진적으로 해를 개선시켜서 문제를 해결한다는 점이 놀라웠다.

볼록껍질을 사용해서 시간을 조금 줄였다.

import sys
import math
input = sys.stdin.readline
n = int(input())
dots = [[float(i) for i in input().split()] for _ in range(n)]
def ccw(p1, p2, p3):
    return p1[0]*(p2[1] - p3[1]) + p2[0]*(p3[1] - p1[1]) + p3[0]*(p1[1] - p2[1])

def monotonechain(dots):
    dots.sort(key=lambda x:(x[0],x[1]))
    if len(dots) <=2:
        return dots

    lower = []
    for d in dots:
        while len(lower) >= 2 and ccw(lower[-2], lower[-1], d) <= 0:
            lower.pop()
        lower.append(d)

    upper = []
    for d in reversed(dots):
        while len(upper) >= 2 and ccw(upper[-2], upper[-1], d) <= 0:
            upper.pop()
        upper.append(d)
    return lower[:-1] + upper[:-1]

if n > 1:
    important = monotonechain(dots)
    xSum = 0
    ySum = 0
    for i in range(n):
        xSum += dots[i][0]
        ySum += dots[i][1]
    x = xSum/n
    y = ySum/n
    ratio = 0.1
    for _ in range(30000):
        maxIn = 0
        maxVal = (x - important[0][0])**2 + (y - important[0][1])
        for i in range(len(important)):
            if (tmp:= (x - important[i][0])**2 + (y - important[i][1])**2) > maxVal:
                maxVal = tmp
                maxIn = i
        x += (important[maxIn][0] - x)*ratio
        y += (important[maxIn][1] - y)*ratio
        ratio *= 0.999
    print(f'{x} {y} {math.sqrt((x - important[maxIn][0])**2 + (y - important[maxIn][1])**2)}')
else:
    print(f'{dots[0][0]} {dots[0][1]} 0')

 

백준 1194번-달이 차오른다 가자. 다음으로 좋아하는 문제가 됐다.

위에서 세번째까지는 잘못된 방법(가장먼점 두개 찾고 원만들기)을 놓지 못해서 틀렸고,

위에서 두번째는 블로그에서 힌트만 얻고 혼자 구현해봤는데, ratio값을 점점 줄여야 하는 것을 몰라서 그냥 상수 $\frac{1}{1000000}$를 곱해버린 것과, 결정적으로 거리 공식을 잘 못써서.. y부분에서 제곱을 빼먹었다...

그래서, 해가 이상하게 가는 문제가 있었다.