TopCoder

Thumb 5b3
Nekosyndrome
かわいいは正義!

User's AC Ratio

50.0% (1/2)

Submission's AC Ratio

16.7% (1/6)

Description

2050 年美國太空總署太空人從火星探險任務帶回了一個看起來很高科技的遊戲機。
經過專家們的檢測,該遊戲機似乎是火星人拿來訓練邏輯思考用的工具。專家們已經能夠解讀的資訊如下:

此遊戲機似乎是一個平面棋盤,每次啟動時就會在棋盤上方出現一些紅色與黑色棋子的全席圖像 (hologram),
簡單來說就是 3D 立體圖像。右圖是該棋盤正上方鳥瞰圖,黑色棋子以空心的正方格代表,共五個,紅色棋子
以實心的圓形點代表,共六個。這時如果選定 p 個黑色棋子,以手將這些 p 個黑色棋子為端點,畫出一個 p 多邊形,
則紅色棋子就被分為兩群,一群在多邊形內,另外一群在多邊形外。在多邊形內(含在多邊形線上)的紅色棋子就會全部消失,
然後一些符號就顯示在多邊形內。

太空總署推測這些符號實際上代表一個數字,而這個數字應該是與剩下的棋子有關。經過實驗,太空總署認為如果將每一個剩下
的紅色棋子以 111 分計算,而多邊形上的每一個黑色棋子(多邊形的端點)以 20 分計算,則顯示在中央的符號應該就是這些
分數的總和。而當此總和是所有可能(多邊形)的最低分時,美妙的音樂就會響起。請寫一個程式幫助太空總署驗證此理論的正確性。

                 

※條件限制
1. 遊戲機棋盤大小為 1,000 x 1,000。
2. 棋盤上黑色棋子數為 b, 3 ≦ b ≦ 100,紅色棋子數為r, 3 ≦ r ≦ 100。
3. 黑色棋子與紅色棋子皆落在棋盤整數座標位置。同一個座標位置僅能有一個黑色或紅色棋子。

Input Format

檔案第一行有兩個整數分別代表 b 及 r。接下來的b 行,每行有兩個整數,代表一個黑色棋子的(x, y)座標。
再接下來的r 行,每行有兩個整數,代表一個紅色棋子的(x, y)座標。

Output Format

輸出音樂響起時棋盤中間符號所應代表的數字。

Sample Input

5 6 << 5 顆黑棋子、6 顆紅棋子
50 500 << 5 顆黑色棋子的座標
150 950
600 50
950 500
950 950
100 50 << 6 顆紅色棋子的座標
100 950
150 500
150 600
600 200
600 500

Sample Output

302 << 2 * 111 + 4 * 20 = 302

Hints

Problem Source

原TIOJ1580 / 台北市 97 學年度高級中學資訊學科能力競賽

Subtasks

For Testdata: 0 ~ 0, Score: 20
For Testdata: 1 ~ 1, Score: 20
For Testdata: 2 ~ 2, Score: 20
For Testdata: 3 ~ 3, Score: 20
For Testdata: 4 ~ 4, Score: 20
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 3000 65536 262144
1 3000 65536 262144
2 3000 65536 262144
3 3000 65536 262144
4 3000 65536 262144