BOJ 27516 - 과녁 맞추기 (Python3)

넓은 분야의 수학 문제를 이것저것 얕게 손대다 보면 본의 아니게 잡지식이 늘게 된다.

부호를 보존하는 제곱을 계산하는 방법이라거나, 쓸데없는 계산을 우회해서 계산하는 경우의 수를 비약적으로 줄인다거나. 런타임 전의 전처리에 가까운 분야이기는 하지만, 하여튼 그러하다.

 

이번 문제는 2월 26일에 개최된 제1회 흐즈로컵 C번 문제이다. 나는 실수하기는 쉬우나 그렇게 어려운 문제는 아니라고 보았는데, 다른 사람들은 그렇지 않다 생각했나 보다.

 

그럼 본격적으로 풀이에 돌입해 보자.

---

문제

흐즈로는 현재 2차원 좌표평면에서 \((x,y)\)에 위치한 전망대에 있습니다. 전망대 주변에는 \(n\)개의 과녁이 존재합니다. 각각의 과녁은 크기가 없는 점으로 취급합니다. 흐즈로는 공을 던져서 과녁을 맞추고자 합니다. 이 때, 흐즈로와 흐즈로가 던진 공, 그리고 과녁은 다음과 같은 규칙을 따릅니다.

1. 흐즈로는 공을 \(x\)축에 평행하게 던집니다. 따라서, 흐즈로가 공을 던질 수 있는 방향은 좌측 또는 우측 2가지만 존재합니다.

2. 흐즈로가 공을 던지는 속도는 임의로 정할 수 있습니다. 단, \(0\) 또는 \(\infty\)의 속도로 던질 수는 없습니다.

3. 흐즈로가 던진 공은 포물선 운동을 합니다. 다시 말해, \(x\)축 방향의 속도는 일정하며, \(y\)축 방향의 속도는 연직 아래쪽 방향으로, \(g=9.806 \text{m} / \text{s}^2\)의 가속도로 가속합니다.

4. 흐즈로가 존재하는 좌표계에서는 \(1\)을 \(1\text m\)로 취급하며, 거리는 유클리드 거리를 따릅니다. 다시 말해, \((0,0)\)과 \((1,0)\) 사이의 거리는 \(1\text{m}\)입니다.

5. 흐즈로가 던진 공이 과녁을 맞추더라도, 공의 궤적은 바뀌지 않습니다. 다시 말해, 과녁을 맞추더라도, 물리적인 의미의 "충돌"로 취급하지는 않습니다.

6. 흐즈로와 과녁의 좌표는 모두 정수입니다. 이때, 모든 좌표의 범위는 \(-10^8 \le x,y \le 10^8\)입니다.

7. 같은 좌표에 과녁이 두 개 이상 존재할 수도 있습니다. 단, 흐즈로가 존재하는 좌표에는 과녁이 존재하지 않습니다.

흐즈로는 공 하나로 맞출 수 있는 과녁의 최대 개수가 몇 개인지 궁금했습니다. 흐즈로와 과녁의 좌표가 주어질 때, 맞출 수 있는 과녁의 최대 개수를 출력하세요.

 

입력

첫 번째 줄에 흐즈로의 좌표를 나타내는 두 정수 \(x, y\) \(( -10^8 \le x,y \le 10^8)\)가 공백으로 분리되어 주어집니다.

두 번째 줄에 과녁의 개수를 나타내는 양의 정수 \(n\) \(( 1 \le n \le 10^5)\)이 주어집니다.

세 번째 줄부터 \(n+2\)번째 줄까지 \(n\)개의 줄에 \(i\)번째 과녁의 좌표를 나타내는 두 정수 \(x_i, y_i\) \(( -10^8 \le x_i ,y_i \le 10^8)\)가 공백으로 분리되어 주어집니다.

 

예제 입력)

0 0
5
1 1
1 -1
2 -4
1 -4
-1 -4

 

출력

문제의 정답을 한 줄에 출력하세요.

 

예제 출력)

2

우측으로 약 \(2.21427188935776358060245537 \text{m/s}\)의 속도로 공을 던지면 \((1,-1), (2,-4)\)에 있는 과녁을 맞출 수 있습니다.

---

내 코드

from sys import stdin
from math import gcd
input = stdin.readline
x,y = map(int,input().split()); data = {}
for _ in range(int(input())):
    a,b = map(int,input().split())
    u,v = a-x,y-b
    if v > 0 and u != 0:
        w = u*abs(u); d = abs(gcd(w,v))
        p = (w//d,v//d)
        try: data[p] += 1
        except: data[p] = 1
print(max(data.values()) if len(data) > 0 else 0)

 

일단 \(x, y\)를 입력받아 흐즈로의 좌표로 둔다. 여기서, 흐즈로가 맞힐 수 있는 과녁들의 좌표는 어떻게 될까? 과녁 좌표를 \((a,b)\)라고 두어 보자.

일단 x좌표가 흐즈로의 x좌표와 같은 과녁은 맞힐 수 없다. 수직 아래로 떨궈야만 맞을 텐데, 초기속력 0으로 둘 수 없기 때문이다. 또한, y좌표가 흐즈로의 y좌표보다 크거나 같 과녁은 맞힐 수 없다. 항상 수평으로 던지기 때문에, 궤적은 \(b=y-k(x-a)^2\) \((k>0)\)의 꼴로 아래로 볼록한 포물선의 모양을 가질 것이기 때문이다.

따라서, 방금 저 포물선의 식을 변형해서, \(k(a-x)^2=y-b\)로 바꾸고, 변수를 치환해 보자. \(u=a-x, v=y-b\)로 말이다. 그러면 적당한 양수 \(k\)가 존재해서 \(ku^2=v\)가 만족할 것이다. 이 \(k\)들을 모조리 저장한 다음 가장 많이 중복된 횟수를 구하여 답을 내면 된다.

정말 그럴까?

 

아니다!

같은 \(k\)값을 가진다 하더라도, 초기에 흐즈로의 왼쪽에 위치한 과녁과 오른쪽에 위치한 과녁은 동시에 맞힐 수 없다. 위 예제에서, 만일 \((-1,-1)\)의 좌표를 가진 과녁이 하나 있다고 답이 3개가 되지는 않는다. 따라서 \(u\)의 부호에 따라서 \(k\)를 다르게 파악해야 한다.

\(k=\frac{v}{u^2}\)이 된다. u의 부호와 상관없이 \(k\)는 항상 양수가 된다는 소리다. 그러면 \(u\)가 음수일 때 \(k\) 역시 음수가 되게 할 수 있을까? 여기서 필요한 것이 바로 부호를 보존하는 제곱이다.

\(w=u|u|\)는 \(u^2\)과 절댓값이 같고, \(u\)와 부호가 같다. 따라서 새로운 \(K=\frac vw\)라는 변수를 도입하면, 이 \(K\)가 같은 과녁들끼리는 한 번의 투척으로 모조리 맞힐 수 있다.

그냥 나누면 실수오차 때문에 틀릴 수가 있다. 그러면 순서쌍으로 저장하는 것은 어떨까. 기약분수로 나타낸 다음, 분모와 분자를 분리하여 tuple로 저장하면 dictionary 안에 저장할 수 있다. list는 dictionary의 key로 쓸 수 없으니...

input만 빠르게 받아준다면, PyPy의 힘을 빌리지 않고서도 충분히 빠른 시간 안에 맞힐 수 있다.

 

이로서 27516번의 풀이를 마친다.

그럼, 오늘도 당신의 코딩 실력이 상승하기를.