만드는 중입니다

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

평면 게임

면접 대비

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

요약
N개의 점을 임의로 회전·평행이동해 최대한 많은 점이 두 좌표축 위에 놓이도록 할 때, 없앨 수 있는 점의 최대 개수를 구한다.
난이도

보통10점 중 6점

유형
기하, 완전 탐색, 조합론, 해시맵
정답자
아직 제출이 없습니다

문제

영선이는 평면 게임을 한다. 이차원 좌표평면 위에서 하는 게임이다. 처음에 평면에는 점이 NN개 놓여 있고, ii번째 점의 좌표는 (xi,yi)(x_i, y_i)이다.

목표는 총을 한 번 쏘아서 점을 최대한 많이 없애는 것이다. 영선이가 총을 쏘면 xx축 위에 있는 점과 yy축 위에 있는 점이 모두 사라진다.

총을 쏘기 전에 영선이는 다음 두 연산을 원하는 순서로 0번 이상 수행할 수 있다.

  • 모든 점을 동시에 임의의 방향 벡터만큼 평행이동시킨다.
  • 모든 점을 동시에 원점을 중심으로 임의의 각도만큼 회전시킨다.

영선이가 없앨 수 있는 점의 최대 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 점의 개수 NN이 주어진다. (1≤N≤501 \le N \le 50)

둘째 줄부터 NN개 줄에 각 점의 좌표 xix_i와 yiy_i가 공백 하나로 구분되어 주어진다. (−1,000,000≤xi,yi≤1,000,000-1{,}000{,}000 \le x_i, y_i \le 1{,}000{,}000, 모든 좌표는 정수)

좌표가 같은 점이 여러 번 주어질 수 있고, 이런 점도 각각 다른 점으로 센다.

출력

첫째 줄에 영선이가 없앨 수 있는 점의 최대 개수를 출력한다.

예제4

  1. 예제 1

    입력
    2
    0 0
    5 5
    
    예상 출력
    2
    
  2. 예제 2

    입력
    5
    0 0
    -1 -1
    1 -1
    1 1
    -1 1
    
    예상 출력
    5
    
  3. 예제 3

    입력
    5
    0 0
    0 1
    0 -1
    1 0
    -1 0
    
    예상 출력
    5
    
  4. 예제 4

    입력
    9
    0 0
    -3 -3
    3 -3
    3 3
    -3 3
    0 3
    0 -3
    3 0
    -3 0
    
    예상 출력
    5