Polylops

시간 제한1초메모리 제한128 MB

요약
단순 다각형의 꼭짓점이 주어질 때, 다각형을 자기 자신으로 되돌리는 대칭축의 개수를 센다.
난이도

보통10점 중 7점

유형
기하, 문자열 매칭, 구현
정답자
아직 제출이 없습니다

문제

180도인 각, 길이가 0인 변, 자기 교차가 없는 (그러나 반드시 볼록할 필요는 없는) 단순 다각형의 꼭짓점들이 순서대로 주어진다. 이 다각형이 가지는 서로 다른 대칭축의 개수를 구하여라.

대칭축이란, 그 직선을 기준으로 다각형을 반사시켰을 때 다각형이 자기 자신과 정확히 겹치게 되는 직선을 말한다.

입력

입력은 여러 개의 다각형에 대한 설명으로 이루어진다.

각 다각형의 설명은 두 줄로 주어진다. 첫 번째 줄에는 다각형의 꼭짓점 개수를 나타내는 정수 nn (3≤n≤10003 \le n \le 1000)이 주어진다. 두 번째 줄에는 다각형의 꼭짓점을 순서대로 나타내는 nn개의 좌표 쌍(각각 xx 값과 yy 값)이 주어진다. 모든 좌표는 −1000-1000 이상 10001000 이하의 정수이다.

입력은 꼭짓점이 00개인 다각형으로 끝난다.

출력

각 다각형마다 한 줄씩 Polygon #x has y symmetry line(s). 형식으로 출력한다. 여기서 xx는 (1부터 시작하는) 다각형의 번호이고, yy는 그 다각형이 가지는 서로 다른 대칭축의 개수이다.

예제2

  1. 예제 1

    입력
    4
    -1 0 0 2 1 0 0 -1
    3
    -666 -42 57 -84 19 282
    3
    -241 -50 307 43 -334 498
    0
    
    예상 출력
    Polygon #1 has 1 symmetry line(s).
    Polygon #2 has 0 symmetry line(s).
    Polygon #3 has 1 symmetry line(s).
    
  2. 예제 2

    입력
    4
    0 0 4 0 4 4 0 4
    0
    
    예상 출력
    Polygon #1 has 4 symmetry line(s).