만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

날끝

면접 대비

시간 제한2초메모리 제한1024 MB

요약
각 팁의 x_i + y_i 값이 서로 다르도록 고를 수 있는 최대 개수를 구합니다.
난이도

쉬움10점 중 3점

유형
해시맵, 구현
정답자
아직 제출이 없습니다

문제

로건은 다가오는 전투를 생각하다가 날끝을 달면 승률을 크게 높일 수 있다고 판단했다. 그래서 날끝 세트를 통째로 주문하기로 했다.

세트는 nn개의 날끝으로 구성된다. 완벽한 물건은 없어서, ii번째 날끝은 두 정수의 쌍 (xi,yi)(x_i, y_i)로 표현된다. xix_i는 강화하는 능력의 개수이고, yiy_i는 약화하는 능력의 개수이다. 로건은 세트의 일부만 고르기로 했다. 선택한 부분 집합에서 서로 다른 두 날끝 ii, jj(i≠ji \neq j)에 대해 항상 xi−yj≠xj−yix_i - y_j \neq x_j - y_i가 성립하면, 그 부분 집합을 최대로 효율적이라고 한다.

로건이 전투 직전에 알고 싶은 것은, 최대로 효율적인 부분 집합으로 고를 수 있는 날끝의 최대 개수이다.

입력

첫 줄에 원래 세트에 있는 날끝의 개수인 자연수 nn이 주어진다 (1≤n≤1051 \le n \le 10^5).

다음 nn개의 줄에는 각각 ii번째 날끝을 나타내는 두 정수 xix_i, yiy_i가 주어진다 (1≤xi,yi≤1091 \le x_i, y_i \le 10^9).

출력

답을 한 줄에 출력한다.

예제1

  1. 예제 1

    입력
    5
    4 5
    2 8
    1 3
    7 3
    6 5
    
    예상 출력
    4