No.3008 One-Person Security Guard
タグ : / 解いたユーザー数 10
作問者 :
ジュ・ビオレ・グレイス
/ テスター :
👑 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もしくは右上の雲マークをクリックしてアカウントを作成してください。