acm International Collegiate Programming Contest

Links

A B C D E F G H

Problem F

紋章の形の別荘

お姫様は広大な私有地を持っており,そこに新たに別荘を建設することにした.

お姫様の発案で,別荘の母屋の 1 階部分を王家の紋章に由来する外形とすることになった. 紋章は単純多角形である.紋章の例を 4 つ図 F-1 に示す. 外形は必ずしも紋章と同じ形である必要はなく,図 F-2 のように紋章の複製を複数個ずらして重ね合わせた図形でも良い.有限個ならいくつの複製を重ね合わせてもよいが,全ての複製は同じ大きさかつ同じ向きでなければならず,裏返してはいけない.

データセット 1 データセット 2 データセット 3 データセット 4
図 F-1: Sample Input の紋章
図 F-2: Sample Input の最初のデータセットにおける,重ね合わせ方の例

防犯上,外形は凸多角形にしたい.図 F-2 の右端の図形は凸多角形になっている. あなたの仕事は,紋章を有限個重ね合わせることで凸多角形を作成できるかを判定することだ.

Input

入力は複数のデータセットからなる. 各データセットは次の形式で表される.

n
x1 y1
 ⋮
xn yn

n は紋章を構成する頂点の個数で,3 以上 200 以下の整数である.(xi, yi) は右手座標系で i 番目の頂点の座標を表す (i = 1, …, n).xiyi は,それぞれ整数であり,−10000 以上 10000 以下である.頂点同士の座標は異なり,反時計回り順に与えられる.紋章を構成する辺同士は接続する頂点以外に共有点を持たない.また,どの頂点でも辺同士のなす角度が 180 度ではない.

入力の終わりは,1 つのゼロだけからなる行で表される.データセットの個数は 500 を超えない.

Output

各データセットについて,凸多角形を作成できるならば Yes を,できないならば No を 1 行に出力せよ.

Sample Input

12
-5 -7
5 -7
5 -3
1 -3
1 3
5 3
5 7
-5 7
-5 3
-1 3
-1 -3
-5 -3
7
0 0
7 1
3 2
2 4
6 9
4 10
1 7
14
0 1
2 0
3 1
2 4
0 4
1 2
-1 1
0 3
-1 4
-2 4
-3 3
-2 -3
-1 -3
0 -2
5
-2 0
1 -4
2 -3
2 3
1 4
0

Output for the Sample Input

Yes
No
Yes
Yes
(End of Problem F) A B C D E F G H