평면 게임

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

보통6기하완전 탐색조합론해시맵면접 대비아직 제출이 없습니다시간 제한2초메모리 제한512 MB

문제

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

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

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

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

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

입력

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

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

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

출력

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