아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

Symmetry of Stars

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

요약
서로 다른 n개의 점이 주어질 때, 한 중심점을 기준으로 짝을 이루는 점의 최대 개수를 구한다.
난이도

보통10점 중 6점

유형
해시맵, 기하, 수학
정답자
아직 제출이 없습니다

문제

Twinkling Stars in the universe attract us, guide us, and shed numerous intuitions to us. Astronomer Dr. Kobserved twinkling stars in a dark sky. One day, he was curious of symmetry of stars. To simplify the problem, he assumed the sky is a xyxy plane and the stars are points placed on the plane. When the set of stars SS and a point p=(p_x,p_y)p = \left(p\_x, p\_y \right) are given, symmetry of stars SS with respect to a point pp is defined as the number of points (x,y)∈S(x, y) \in S such that there exists at least one point (x′,y′)∈S(x', y') \in S which satisfies (x+x′2,y+y′2)=(p_x,p_y)\left( \frac{x+x'}{2}, \frac{y+y'}{2} \right) = \left(p\_x, p\_y\right). When the set of stars SS is given, symmetry of stars SS is defined as the maximum symmetry of stars SS with respect to any point pp in the whole xyxy plane. Let’s see an example following.

In the example above, we are given a set of stars S=(1,3),(3,1),(−1,2),(4,4),(1,1),(3,3)S = \\{(1,3), (3,1), (-1,2), (4,4), (1,1), (3,3)\\}. The symmetry of stars SS with respect to a point p=(2,2)p = (2,2) is 44 since the point a=(1,3)a = (1,3) has point b=(3,1)b = (3,1) which satisfies (a_x+b_x2,a_y+b_y2)=(1+32,3+12)=(p_x,p_y)=(2,2)\left( \frac{a\_x + b\_x}{2}, \frac{a\_y + b\_y}{2} \right) = \left( \frac{1+3}{2}, \frac{3+1}{2} \right) = \left( p\_x, p\_y \right) = (2, 2) and the point e=(1,1)e = (1,1) has point f=(3,3)f = (3,3) which satisfies (e_x+f_x2,e_y+f_y2)=(1+32,1+32)=(p_x,p_y)=(2,2)\left( \frac{e\_x + f\_x}{2}, \frac{e\_y + f\_y}{2} \right) = \left( \frac{1+3}{2}, \frac{1+3}{2} \right) = \left( p\_x, p\_y \right) = (2, 2). The symmetry of stars SS with respect to a point p=(−1,2)p =(-1,2) is 11 since the point c=(−1,2)c = (-1,2) has point c=(−1,2)c = (-1,2) itself which satisfies (c_x+c_x2,c_y+c_y2)=(−1−12,2+22)=(p_x,p_y)=(−1,2)\left( \frac{c\_x +c\_x}{2}, \frac{c\_y + c\_y}{2} \right) = \left( \frac{-1-1}{2}, \frac{2+2}{2} \right) = \left( p\_x, p\_y \right) = (-1, 2). The symmetry of stars SS is 44 since the symmetry of stars SS with respect to the point p=(2,2)p = (2, 2) is the maximum among all the points in the xyxy plane.

Given a list of nn distinct points that represent stars, write a program to output the symmetry of the given stars.

입력

Your program is to read from standard input. The input starts with a line containing one integer, nn (1≤n≤3,0001 ≤ n ≤ 3\\,000), where nn is the number of stars. The stars are numbered from 11 to nn. In the following nn lines, the ii-th line contains two integers that represent xx (−109≤x≤109-10^9 ≤ x ≤ 10^9) and yy (−109≤y≤109-10^9 ≤ y ≤ 10^9) coordinates of the star ii, repectively. Note that no two stars are in the same position.

출력

Your program is to write to standard output. Print exactly one line. The line should contain the symmetry of stars.

예제3

  1. 예제 1

    입력
    6
    1 3
    3 1
    -1 2
    4 4
    1 1
    3 3
    
    예상 출력
    4
    
  2. 예제 2

    입력
    5
    1 3
    3 1
    1 1
    3 3
    2 2
    
    예상 출력
    5
    
  3. 예제 3

    입력
    1
    1 5
    
    예상 출력
    1