백준 20157(화살을 쏘자!) - 해결

화살을 쏘자!

 

문제

호준이는 요즘 활 쏘기에 푹 빠져 있다. 열심히 활 쏘기를 연습하던 호준이는 쏠 때 마다 10점이 나오는 경지에 이르렀다. 이렇다 보니 한 방향으로 있는 과녁에 쏘는 것에 실증을 느낀 호준이는 새로운 방식의 활 쏘기를 시도해 보기로 하였다.

화살이 꽂힌 위치에 따라 점수를 얻는 기존의 방식과 다르게 2차원의 넓은 공터에 풍선을 (x, y)지점에 설치해 두고 지정된 위치 (0, 0) 에서 원하는 방향으로 화살을 쏜다. 화살은 진행 방향으로 무한히 뻗어 나갈 수 있으며, 이 화살이 날아가며 터트린 풍선의 수만큼 점수를 얻기로 했다. 풍선 한 개당 점수는 1점으로 동일하고 같은 위치에 2개 이상의 풍선을 둘 수 없다. 또한 호준이가 서있는 (0, 0)에도 풍선을 둘 수 없다.

호준이는 신중하게 방향을 설정해 한발을 쐈고, 자신이 선택하여 쏜 방향이 최선의 방향인지 궁금해진 호준이는 화살 하나로 얻을 수 있는 최대 점수가 궁금해졌다. 활쏘기 연습하느라 바쁜 호준이를 대신해서 풍선의 위치가 주어진다면 화살 한 개를 쏘아 얻을 수 있는 가장 높은 점수를 알려주자.

 

입력

첫번째 줄에 풍선의 개수 정수 N(1 ≤ N  ≤ 100,000)이 주어진다.

다음 N개의 줄에는 풍선의 위치인 두 정수 x, y (-1,000,000 ≤ x, y ≤ 1,000,000)가 주어진다.

 

출력

 

첫번째 줄에 화살 한 개를 쏘아 얻을 수 있는 최대 점수를 구해 출력한다.

---

사용한 방법은 기울기를 이용한 방법

(0,0)에서 시작하기 때문에 각 풍선의 기울기를 구해서 기울기가 같은 것 끼리 묶는 방법

같은 기울기에 있다는 건 일직선상에 있다는 것이기 때문.

하지만 이렇게 풀었을 때 문제점이 하나 있었다.

같은 기울기더라도 반대편에 있으면 한번에 못 터뜨린다는 것.

그래서 사용한 것은 사분면 별로 나누어서 사용하는 것. x, y 범위를 사용하여서 나누고 x와 y가 0인 경우는 각 사분면에 하나씩 따로 저장하는 방식을 사용.

그리고 그중 가장 큰 값을 뽑아내는 방식

'''
화살을 쏘자!

'''
import sys
input = sys.stdin.readline
from collections import defaultdict

N = int(input())

# 사분면 나누기
# 빈 리스트를 없애기 위해서 0을 추가
# 그리고 1개는 무조건 있기 때문에 1로 추가
quadrant1 = defaultdict(int)
quadrant1[0] += 1
quadrant2 = defaultdict(int)
quadrant2[0] += 1
quadrant3 = defaultdict(int)
quadrant3[0] += 1
quadrant4 = defaultdict(int)
quadrant4[0] += 1
# 하나씩 사분면을 기준으로 나누고
# 기울기를 비교하면서 저장
for _ in range(N):
    x, y = map(int,input().split())
    # 1사분면
    if x > 0 and y >= 0:
        # x축에 있을 경우
        if y == 0:
            quadrant1['v'] += 1
        # 나머지
        else:
            quadrant1[y/x] += 1
    # 2사분면
    elif x <= 0 and y > 0:
        if x == 0:
            quadrant2['v'] += 1
        else:
            quadrant2[y/x] += 1
    # 3사분면
    elif x < 0 and y <= 0:
        if y == 0:
            quadrant3['v'] += 1
        else:
            quadrant3[y/x] += 1
    # 4사분면
    elif x >= 0 and y < 0:
        if x == 0:
            quadrant4['v'] += 1
        else:
            quadrant4[y/x] += 1
# 그 값중에 가장 큰 값
print(max(max(quadrant1.values()),max(quadrant2.values()),max(quadrant3.values()),max(quadrant4.values())))