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

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

대칭

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

요약
서로 다른 격자점 1000개 이하가 주어질 때, 어떤 점이나 직선에 대해 대칭이 되도록 추가해야 하는 점의 최소 개수를 구한다.
난이도

어려움10점 중 8점

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

문제

할 일이 없어 앞쪽 벽에 찍힌 점 무늬를 한참 들여다본다. 무늬에는 눈에 띄는 대칭이 없다. 시간이 지날수록 그 사실이 거슬려서, 점을 몇 개 더 찍어 균형을 맞추려고 한다. 이 일을 프로그램으로 해결한다.

좌표가 −20000-20000 이상 2000020000 이하인 점이 여러 개 주어진다. 무늬 전체가 대칭을 이루도록 만들 때 추가로 찍어야 하는 점의 최소 개수를 구한다. 대칭은 한 점을 중심으로 하는 점대칭이거나, 한 직선을 축으로 하는 선대칭이다. 점대칭이면 중심이 주어진 점 중 하나일 필요가 없고, 중심의 좌표가 정수일 필요도 없다. 선대칭이면 축의 기울기는 무엇이든 된다. 새로 찍는 점의 좌표는 −20000-20000 이상 2000020000 이하가 아니어도 된다.

입력

첫째 줄에 점의 개수 nn (1≤n≤10001 \le n \le 1000)이 주어진다.

이어지는 nn개 줄에는 점의 좌표 xx와 yy (−20000≤x,y≤20000-20000 \le x, y \le 20000)가 공백으로 구분되어 주어진다. 모든 점의 위치는 서로 다르다.

출력

모든 점이 어떤 점에 대해 점대칭이거나 어떤 직선에 대해 선대칭이 되도록 추가해야 하는 점의 최소 개수를 한 줄에 출력한다.

예제2

  1. 예제 1

    입력
    4
    0 0
    1000 0
    0 1000
    1000 1000
    
    예상 출력
    0
    
  2. 예제 2

    입력
    11
    0 0
    70 100
    24 200
    30 300
    480 400
    0 100
    0 200
    0 400
    100 0
    300 0
    400 0
    
    예상 출력
    6