[BOJ 20157, Python 3] 화살을 쏘자!

https://www.acmicpc.net/problem/20157

20157번: 화살을 쏘자!

 

 

풀이

좌표평면에서 한 방향으로 화살을 쏜다는 것은 기울기가 설정되어 있다는 뜻입니다.

그래서 제 1사분면부터 제 4사분면까지 defaultdict를 만들어주고, 각 좌표의 최대공약수를 통해 기울기를 구해주고 조건에 맞는 사분면에 넣어주면 됩니다.

x = 0 혹은 y = 0일 때는 따로 변수를 둬서 구해주고, 여기에 있는 값들중 최댓값을 구해주면 됩니다.

 

 

코드

from math import gcd
from collections import defaultdict as dfd
input = __import__('sys').stdin.readline
one = dfd(lambda : 0)
two = dfd(lambda : 0)
three = dfd(lambda : 0)
four = dfd(lambda : 0)
plus_x, minus_x, plus_y, minus_y = 0, 0, 0, 0
n = int(input())
for i in range(n):
    x, y = map(int, input().split())
    if x == 0:
        if y > 0: plus_y += 1
        else: minus_y += 1
        continue
    if y == 0:
        if x > 0: plus_x += 1
        else: minus_x += 1
        continue
    vx, vy = abs(x), abs(y)
    g = gcd(vx, vy)
    nx, ny = vx // g,  vy // g
    if x > 0 and y > 0: one[str(nx)+'/'+str(ny)] += 1
    if x < 0 and y > 0: two[str(nx)+'/'+str(ny)] += 1
    if x < 0 and y < 0: three[str(nx)+'/'+str(ny)] += 1
    if x > 0 and y < 0: four[str(nx)+'/'+str(ny)] += 1
ans = 0
if len(one.values()) > 0: ans = max(ans, max(one.values()))
if len(two.values()) > 0: ans = max(ans, max(two.values()))
if len(three.values()) > 0: ans = max(ans, max(three.values()))
if len(four.values()) > 0: ans = max(ans, max(four.values()))
print(max(ans, plus_x, minus_x, plus_y, minus_y))