TopCoder

Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

66.7% (4/6)

Submission's AC Ratio

20.4% (10/49)

Tags

Description

在那之後過了半年多。(詳情請見TOIJ 1835)
你,妹可,今天也努力的想變成溫拿。

「喔膩醬....夏梨明明這麼相信喔膩醬......」
「等等!夏梨!妳聽我解釋......!」
「喔膩醬!.......最討厭了......!!!」
夏梨說完,哭著跑出了房間,留下你獨自一個人。
.
.
.
不,你不是一個人...
「喔膩醬~~那個女生是你的朋友嗎?」你身邊的金髮小蘿莉看著你,露出了不知是開心還是生氣的微笑。

「請....聽我解釋....」
「好啊!那就請喔膩醬你,好,好,的,解,釋,吧~」
你的前途一片黑暗。
.
.
.
為什麼會變成這個樣子呢?
時間拉回到前一天晚上。

前一天晚上,你,妹可,正在查詢第二天要進行的天龍國古可魚語聽力測驗考場資訊,卻意外的發現你可以查出每個考生的性別、電話和當天考試的座標!

於是你想了一個邪惡的計畫,你決定打電話給和你同一個考場的所有女生,約她們考完出來一起吃午餐。
可是正當你要拿起電話時,你發現了一個嚴重的問題,你不知道這個女生是不是和你在同一個考場!

天龍國的古可魚語聽力測驗考試場地和某些老是出問題的競賽測驗場地不同,會提供考生優良的環境和絕對公平的測驗,為了讓所有人都可以清楚的聽到題目內容,考場特別設計成了一個環繞的結構,並裝上吸音棉減少回音干擾。根據結果看來,我們可以確定考場的形狀是一個簡單凸多邊形。
而所有的考生坐落在數個考場中,你並不知道她們的考場,只知道她們當天考試的座標位置,而你想要計算出所有的女生中和你同一個考場的有哪些人,這樣她才能在結束的時候約她們。
很幸運的,你成功的拿到了考場的結構圖,上面記錄了考場的角的座標,你可以用這些點組成一個凸多邊形,也就是考場的範圍。

很不幸的,你取得的資料雖然是完整的,但是經過了加密。
但是又很慶幸的,看來設計系統的人並不知道什麼是加密,又或者是他們的系統不會自動換行,所以資料被加了一些多餘的空白和換行字元,不過對你來說並不構成威脅。
由於考場太多了,而且你又想順便研究其他考場,也許之後也可以順便約她們,所以你決定找出對於每個考場來說,哪些人在考場裡,哪些人不在。

Input Format

你拿到的檔案有多組,每一組代表一個考場。
資料中每個字串、數字之間都有多個空白和換行字元,且出現沒有一定的規律。

一開始會有多組整數數對,分別代表考場的角的座標,按照逆時針排序,接下來會有一些文字,代表考場的資訊,使用天龍國語編寫。

天龍國語包含大小寫26個拉丁字母(但是不包含大寫的Z),並且結尾一定會加上一個大寫Z,詳細的內容可以參考「天龍國語文法解析輕鬆讀」、「三分鐘學會說天龍國語」等等參考書(天龍國各大書局均有販售)。比如這就是一段天龍國語:「Hello world Z」

接下來會有多組整數數對,每組數對代表了一個女生的座標位置,之後會有一段天龍國語紀錄考生的資訊。
在所有考生的資料最後會有一段天龍國語紀錄一些注意事項。

檔案中的數字全部都是介於 -109 到 109 之間的整數,每一句天龍國語的總長度(包含空白和換行)不會超過1000個字元,每個數字和天龍國語之間的間隔(空白和換行)也不會超過100個字元。

你可以相信考場一定是一個最少有3個角,最多有 105 個角的多邊形,並且每個考場後面的女生資料最多不會超過 105 筆。

請參考範例輸入。

Output Format

對於每一個考場,
第一行請輸出考場的形狀是一個幾個角的多邊形(只要檔案中有提到,無論該角的角度是多少都算)
接下來,對於每個女生的座標,輸出她是否在該考場內,如果是請輸出y,否則輸出n。
每個考場結尾請加上一行空行。

請參考範例輸出。

Sample Input 1

0 0
10 0
10 10
0 10
CK ans FS Z
5 5 Ada Z
0 5 Bella SS Z
-1 -1 Charlotte Z
8 8 Kanzaki H Aria Z
END Z

-1 -1 0
0
-1 0 Z
1 1 Ha HaZ
2 2 HaHa Ha Ha HA Z
Geez END
Z

Sample Output 1

4
y
y
n
y

3
n
n

Hints

在那之後你很開心了打了第一通電話。
「疑?考完試一起出去嗎?可以呦。」
「ㄟ!真....真的嗎?」
「那,我們就約在門口的那顆櫻花樹下吧,喔~膩~醬~❤」
「怎麼有股不祥的預感....」
「就這樣約好了喔!喔膩醬一定要記得喔,不可以再忘記了喔......」
「疑?妳剛剛有說什麼嗎?唯?....」

...To be continued.


如果你想要在輸入完數字之後,忽略接下來在Z之前的所有字元,你可以試試看 cin.ignore()

Problem Source

2015年建中校內培訓第七次模擬賽

Subtasks

No. Testdata Range Score
1 0 10
2 1 20
3 2~3 70

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1
1 1000 65536 262144 2
2 2000 65536 262144 3
3 2000 65536 262144 3