問題一覧 > 通常問題

No.3008 One-Person Security Guard

レベル : / AI推定難易度 : 1825 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 10
作問者 : ジュ・ビオレ・グレイス / テスター : 👑 p-adic
お気に入りにしたユーザー ProblemId : 11792 / 自分の提出
問題文最終更新日: 2025-01-17 21:49:17
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 455 (順位表) の他の問題:

Problem Statement

Ku○kengo has been put in charge of designing an art museum. He drew a blueprint in the shape of a polyline, obtained by connecting $N$ distinct lattice points $P_n = (X_n, Y_n)$ on the $xy$-coordinate plane with line segments in the order $P_1, \dots, P_N, P_1$.
Let $l_n$ denote the segment $\overline{P_n P_{n+1}}$ ($1 \leq n \leq N, \ P_{N+1} := P_1$). If two different segments $l_n, l_m$ intersect at a point other than their endpoints, we say that the figure "self-intersects". If some three consecutive points $P_{n-1}, P_{n}, P_{n+1} \ (1 \leq n \leq N, \ P_0 := P_N)$ lie on the same line, we say that the figure "has a redundant point".
If the polyline figure of this blueprint self-intersects or has a redundant point, output 0.
Otherwise, that is, when the polyline figure of the blueprint forms a polygon, consider the following. Kengo spent too much of his budget on the design, so he can hire only one security guard. We consider whether the entire interior of the museum can be monitored with no blind spots by placing the single guard at one of the vertices $P_n$ of the museum. That is, output 1 if some $P_n$ can be chosen so that for every point $Q$ of the polygon (including points on its edges and its vertices as well as its interior), the segment $\overline{P_n Q}$ is contained in the polygon, and output -1 if this is impossible.
Since the judging conditions are complicated, we recommend that you read through all the samples.

Input

$N$
$X_1 \ Y_1$
$\vdots$
$X_N \ Y_N$

$3 \leq N \leq 10^3,$
$-10^9 \leq X_n, Y_n \leq 10^9 \ (n = 1, \dots, N).$
Note that $P_1 = (X_1, Y_1), \dots, P_N = (X_N, Y_N)$ are not necessarily given in counterclockwise order.

Output

Print a newline at the end.

Sample

Sample 1
Input
5
-1 0
1 0
1 1
0 0
-1 1
Output
0


The segment connecting $(0, 0), (-1, 1)$ and the segment connecting $(-1, 0), \ (1, 0)$ intersect at a point that is not an endpoint of the latter, so the figure self-intersects. Therefore, 0 is output.

Sample 2
Input
5
1 100
0 0
-1 100
-1 -1
1 -1
Output
1


The entire pentagon can be monitored thoroughly from the origin, so 1 is output.

Sample 3
Input
6
0 0
3 0
2 3
2 1
1 1
0 2
Output
-1


This hexagon is a figure in which a blind spot arises no matter which vertex the guard stands on, so -1 is output.

Sample 4
Input
8
0 0
0 2
1 2
1 1
2 1
2 2
3 2
3 0
Output
-1


This is a polygon shaped like the kanji "凹", and a blind spot arises wherever the guard stands, so -1 is output. Note that the vertices in this sample are not in counterclockwise order.

Sample 5
Input
4
0 0
0 1
0 2
1 1
Output
0

The first three points lie on the same line, so there is a redundant point, and 0 is output.

Sample 6
Input
6
0 0
-1 0
0 2
3 0
2 0
0 -1
Output
1


The entire figure can be monitored from the origin, so 1 is output. Note that the vertices in this sample are not in counterclockwise order.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。