1396 . 線段覆蓋
TopCoder
Tags
Description
「我在這條直線上覆蓋一條線段，結束這一回合。」
這是一個兩個人用線段進行「覆蓋」的遊戲。
每個人都有一條無限長的直線，以及一些長度不盡相等的線段，每一條線段都有必須放置的位置，否則視為無效的放置。
線段與線段之間可以重疊，只要直線上某個位置有被任何一條線段覆蓋到，就算是被覆蓋了。
現在A和B兩人輪流將手上的線段覆蓋到對方的直線上，先將目標區間蓋滿的人就獲勝。A是先手，請問誰會贏呢？
Input Format
輸入檔可能包含多筆測試資料。對於每筆測試資料而言：
第一列有兩個正整數 nA, nB (1≦nA, nB≦100,000)，分別代表A, B所有的線段總數。
第二列開始有 nA 對整數 XAi, YAi，代表A所擁有的第i條線段必須放置的位置。(XAi≦YAi)
然後有 nB 對整數 XBi, YBi，代表B所擁有的第i條線段必須放置的位置。(XBi≦YBi)
最後有兩個整數 X, Y，代表先將 [X, Y]這個區間完全覆蓋的人就獲勝。(X≦Y)
所有數字皆可以用C++裡面的有號int型態儲存。
輸入以EOF作為結束。
Output Format
對於每筆測試資料，若A獲勝則輸出 "A WIN"，若B獲勝則輸出 "B WIN"，若A和B都沒辦法獲勝則輸出 "TIE"。
Sample Input 1
1 1
1 5
2 4
3 4
1 2
1 3
2 6 1 4
1 5
2 1
9 10
10 11
9 10
1 5
1 5
2 4
3 4
1 2
1 3
2 6 1 4
1 5
2 1
9 10
10 11
9 10
1 5
Sample Output 1
A WIN
B WIN
TIE
B WIN
TIE
Hints
Problem Source
原TIOJ1396 / 快樂暑假營第四次練習比賽。Problem Setter：Tmt。
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 16 |
| 2 | 1 | 16 |
| 3 | 2 | 16 |
| 4 | 3 | 16 |
| 5 | 4 | 16 |
| 6 | 5 | 20 |