29. Lacy 的簡單多邊形

Lacy 的簡單多邊形

題目敘述

Lacy 今天學到簡單多邊形, 顧名思義就是簡單的多邊形, 至少 Lacy 是這麼認為的。 簡單多邊形是由 $n$ 個相異的點 $p_1$ - $p_1$ - $p_2$ - ... - $p_n$ - $p_1$ 形成, 除了相鄰的兩條邊共用一個點外, 不存在兩條邊共用一個點。 現在 Lacy 學會 簡單多邊形的定義後, 想要檢查自己依序排的石頭們是否能形成一個簡單多邊形

輸入說明

輸入的第一行包含一個整數 $T(T\leq 100)$，代表接下來有 $T$ 個 Lacy。接下來每個 Lacy 有 $n+1(3 \leq n \leq 100)$行，每個 Lacy 的第1行是 $n$ 表示 Lacy 的 $n$ 顆石頭, 接下來 $n$ 行表示每石頭u依序放的座標 (x,y) $(-10^6 \leq x,y \leq 10^6)$

輸出說明

對於每個 Lacy，輸出一行，如果石頭們可以形成一個簡單多邊形就輸出 "Yes", 否則輸出 "No"

範例輸入

2 3 0 0 1 1 0 2 4 0 0 1 1 1 0 0 1

範例輸出

Yes No

子題一[20%]

$n=3$

子題二[30%]

$ x_i = i $

子題三[50%]

無額外限制

Judge Setting

run-time limit: 1000 ms
memory limit: 1048576 byte
測資數量: 3