問題一覧 > 通常問題

No.3154 convex polygon judge

レベル : / AI推定難易度 : 1200 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 79
作問者 : Cafe1942 / テスター : kazuppa sclara lif4635 kk2a
お気に入りにしたユーザー ProblemId : 12269 / 自分の提出
問題文最終更新日: 2025-05-20 21:39:55
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
Math Cafe 1 (順位表) の他の問題:

Problem Statement

There are $N$ points at distinct positions on a $2$-dimensional coordinate plane, and the coordinates of the $i$-th point $(1 \leq i \leq N)$ are $(X_i,Y_i)$.

Initially, not even $1$ line segment is drawn. Determine whether it is possible to form a strictly convex $N$-gon by repeating $N$ times the operation of choosing $2$ distinct points appropriately and connecting them with a line segment.

What is a strictly convex $N$-gon? An $N$-gon $(3 \leq N)$ in which every interior angle is less than $180$ degrees is called a strictly convex $N$-gon. Be careful about cases where there is a vertex whose interior angle is $180$ degrees.

Constraints

  • $3 \leq N \leq 2 \times 10^{5}$
  • $0 \leq X_i,Y_i \leq 10^9 (1 \leq i \leq N)$
  • $i \neq j \Rightarrow (X_i,Y_i) \neq (X_j,Y_j)$
  • All inputs are integers.

Input

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

Output

Print Yes if a strictly convex $N$-gon can be formed, and No otherwise.

Sample

Sample 1
Input
4
0 0
4 0
3 3
0 4
Output
Yes

Connecting point $1$ and point $4$, point $4$ and point $3$, point $3$ and point $2$, and point $2$ and point $1$ forms a convex $4$-gon. Therefore, print Yes.

Sample 2
Input
4
0 0
1 1
4 0
0 4
Output
No

No matter how the lines are drawn, a convex $4$-gon cannot be formed. Therefore, print No.

Sample 3
Input
5
0 0
2 0
4 0
3 3
0 4
Output
No

Connecting point $1$ and point $2$, point $2$ and point $3$, point $3$ and point $4$, point $4$ and point $5$, and point $5$ and point $1$ forms a convex polygon. However, since point $1$, point $2$, and point $3$ lie on a straight line, point $2$ cannot be regarded as a vertex of a $5$-gon, so this is a convex $4$-gon.

Other than this, no matter how the line segments are drawn, a convex $5$-gon cannot be formed. Therefore, print No.

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