ICPC 2019 Asia Regional –Seoul Problem J- Triangulation > 문제은행 : 정보올림피아드&알고리즘

공지   새로운 정올 베타버전이 공개되었습니다.    자세히보기

4393 : Triangulation

1000 ms   
512 MB   
1 회   
1 회   


A regular n-sided polygon P can be partitioned into n − 2 triangles by adding non-crossing line segments connecting two vertices of P. For example, a square can be partitioned into two triangles, a regular pentagon can be partitioned into three triangles, and a regular hexagon can be partitioned into four triangles. The resulting set of triangles is called a triangulation of P. There exist two or more triangulations of P if n is greater than three.


Once a triangulation T of P is chosen, the distance between two triangles a and b in T is defined to be the number of hops crossing the borders of two adjacent triangles when you travel from a to b. Note that you must stay inside the polygon P, at any time during this travel, that is, it is not allowed to hop crossing the border of P.


For example, the distance of a and d in the triangulation shown in Figure J.1 is three since the triangles, a, b, c, and d, should be visited to travel from a to d, and you have to hop three times crossing borders between triangles.





The diameter of a triangulation T is the maximum of the distances between all pairs of triangles in T. Write a program to find a triangulation of a regular n-sided polygon P whose diameter is the minimum over all possible triangulations and print its diameter.​ 


Your program is to read from standard input. The input starts with a line containing n (3 ≤ n ≤ 1,000,000), where n is the number of sides of the regular n-sided polygon. 


Your program is to write to standard output. Print exactly one line. The line should contain the minimum diameter of the triangulations of a regular n-sided polygon.


입·출력 예


입력 예



출력 예



입력 예



출력 예



경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.