TopCoder

Thumb ya2
赤ずきんチャチャ
もっと心の中を二人見せ合えたなら 答えはつかめるよ

User's AC Ratio

100.0% (3/3)

Submission's AC Ratio

15.1% (8/53)

Description

自從『皮皮歷險記』在資訊社掀起一陣熱潮後,這股熱潮開始向外蔓延,漸漸的,大家已經覺得單機遊戲不夠玩了,在眾多強者的加持下,皮皮寫出了一套網路版的『皮皮歷險記』,但是這個遊戲的規則有著非常大的變革,遊戲的規則大致如下:
這個遊戲一局中同時有K個人參加,每個人可以在NxN棋盤上放置兩隻皮皮,並且因為皮皮之間有相互排斥力,兩隻皮皮不能被放在同一個格子上。全部人都放置完後,最外圈的皮皮(就是凸包上的皮皮)會產生一種神祕的力場,而這種力場奇妙之處在於,若共有偶數隻皮皮被困在這個力場中(在凸包上(不包含邊上)的皮皮不會被困在力場中),則這些皮皮就會自滅,但是若是奇數之皮皮在這個力場中,則會產生一股反擊的力量將外圈的皮皮給消滅。在每次產生完力場後,若自己的皮皮尚未被消滅,就可以重新安排他的位置,如此重複下去,直到最後活下來的1~3隻皮皮就獲勝了。
皮皮將遊戲的外觀架構和各種設定都寫好了之後,卻發現他不會寫最重要的遊戲核心,也就是如何處理哪些皮皮要被消滅,於是便委託聰明的你幫他寫這個程式。

Input Format

輸入可能包含多筆測試資料。
每筆測試資料的第一行有兩個正整數 N, K代表棋盤大小和人數(1 ≦ N ≦ 100,000,000,1 ≦ K ≦ 50,000)。
接下來有K行,每行有一個字串S和四個正整數X1, Y1, X2, Y2,表示參賽者名字和兩隻皮皮的座標,所有座標不會重複。(S不會超過20個字元,1 ≦ X1, Y1, X2, Y2 ≦ N)
當N = K = 0時,代表輸入結束,聰明的你當然不會對它輸出任何資料。

Output Format

請依照輸入順序輸出每個人的名字和他會剩下多少隻皮皮,格式請參考範例測資。

Sample Input

5 3
Pipi 1 1 2 2
Pipi2 0 0 0 3
Pipi3 3 0 1 2
0 0

Sample Output

Pipi:1
Pipi2:2
Pipi3:1

Hints

Problem Source

原TIOJ1257 / INFOR 21st幹部考(prob M)。Problem Setter:peter50216。

Subtasks

No. Testdata Range Score
1 0 10
2 1 10
3 2 10
4 3 10
5 4 10
6 5 10
7 6 10
8 7 10
9 8 10
10 9 10

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 5000 65536 262144 1
1 5000 65536 262144 2
2 5000 65536 262144 3
3 5000 65536 262144 4
4 5000 65536 262144 5
5 5000 65536 262144 6
6 5000 65536 262144 7
7 5000 65536 262144 8
8 5000 65536 262144 9
9 5000 65536 262144 10