Shrinking Polygons hust 14048
Time Limit: Unknown
Memory Limit: Unknown
64bit IO Format: %lld & %llu
[Submit] [Go Back] [Status]
Description
A polygon is said to be inscribed in a circle when all its vertices lie on that circle. In this problem you will be given a polygon inscribed in a circle, and you must determine the minimum number of vertices that should be removed to transform the given polygon into a regular polygon, i.e., a polygon that is equiangular (all angles are congruent) and equilateral (all edges have the same length).
When you remove a vertex v from a polygon you first remove the vertex and the edges connecting it to its adjacent vertices w1 and w2, and then create a new edge connecting w1 and w2. Figure (a) below illustrates a polygon inscribed in a circle, with ten vertices, and figure (b) shows a pentagon (regular polygon with five edges) formed by removing five vertices from the polygon in (a).
In this problem, we consider that any polygon must have at least three edges.
Input
The input contains several test cases. The first line of a test case contains one integerN indicating the number of vertices of the inscribed polygon (3 ≤
N ≤ 10
4). The second line contains
N integers
X
i separated by single spaces (1 ≤
X
i ≤ 10
3, for 0 ≤
i ≤
N -1). Each
X
i represents the length of the arc defined in the inscribing circle, clockwise, by vertex
i and vertex (
i+1) mod
N. Remember that an
arc is a segment of the circumference of a circle; do not mistake it for a
chord, which is a line segment whose endpoints both lie on a circle.
The end of input is indicated by a line containing only one zero.
Output
For each test case in the input, your program must print a single line, containing the minimum number of vertices that must be removed from the given polygon to form a regular polygon. If it is not possible to form a regular polygon, the line must contain only the value -1.
Sample input
3
1000 1000 1000
6
1 2 3 1 2 3
3
1 1 2
10
10 40 20 30 30 10 10 50 24 26
0
Output for the sample input
0
2
-1
5
ACM ICPC::South American Regional 2008
Source
South America 2008-2009
n개의 숫자를 제시하고 최소 몇 번을 합치면 한 무더기의value와 같을 수 있습니다.
큰 소의 방법은hash처리sum[i], 시작점px를 일일이 열거하여 매번 한 무더기의 것과 dd를 탐지한다.sum[end]+t*dd가 모두hash가 도착할 수 있다면 이 해는 ok이다.
#include
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
cocos2d Lua 학습(一)ios에서 루아 함수 호출 및 전참 방법 lua 코드: 출력 결과: lua 호출 C++ 방법: add 함수: lua 코드: 출력 결과: 함수를 호출합니다. 함수를 호출하려면 다음 협의를 따르십시오. 우선, 호출할 함...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.