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

For Testdata: 0 ~ 0, Score: 10
For Testdata: 1 ~ 1, Score: 10
For Testdata: 2 ~ 2, Score: 10
For Testdata: 3 ~ 3, Score: 10
For Testdata: 4 ~ 4, Score: 10
For Testdata: 5 ~ 5, Score: 10
For Testdata: 6 ~ 6, Score: 10
For Testdata: 7 ~ 7, Score: 10
For Testdata: 8 ~ 8, Score: 10
For Testdata: 9 ~ 9, Score: 10
No. Time Limit (ms) Memory Limit (KiB)
0 5000 65536
1 5000 65536
2 5000 65536
3 5000 65536
4 5000 65536
5 5000 65536
6 5000 65536
7 5000 65536
8 5000 65536
9 5000 65536