TopCoder

User's AC Ratio

100.0% (1/1)

Submission's AC Ratio

17.6% (3/17)

Description

大逃殺是個可怕的遊戲。

邪惡的政府組織,把一班的學生丟到一個荒島上(附帶一提,這個荒島的形狀是個邊長為100,000的正方形),並給予武器,
讓他們自相殘殺,直到最後只剩下一個活下來的人。

更可怕的是,除了同學之間的殺戮外,還有恐怖的禁區,每到固定的時間,就會有一些位置成為禁區,只要有人在禁區內,
就會在瞬間向這個世界說再見。

不過呢,現代的學生是很團結的,怎麼可能會互相殘殺呢?:)

而且,在現代,每個人都會利用身邊的電子器材來使用方便的『現代魔法』!

所謂魔法就是利用咒文,連接現實世界以及異世界的物理法則,有別於古典魔法將自己的肌肉通電來發動魔法,現代魔法則是利用矽晶片為基礎來發動魔法。

雖然因為電腦的發達與普遍,現代魔法的效率大大的提升,但是仍不及使用複雜人體發動的古典魔法的威力,所以執行大規模魔法時,
需要較大量的單體同時行動才可以達到顯著的效果,而每台電腦的運算能力則被稱為『魔力』,當然這些魔力也是可以被量化的。

於是他們決定使用大規模的求救魔法,來想辦法與外界聯繫。

這個魔法是這樣的,首先要選一些施法的人,這些施法的人將會圍成一個凸多邊形(都位於頂點),並且將其他所有人包在裏頭或多邊形的線上,
才能確保所有人都被外界得知。

非施法者利用自己的電腦提供運算基礎,量化的計算方式是每台電腦的魔力值絕對值和,而這又被稱為魔法的基礎值。

施法者的責任重大,他們將會兩個為一組共同施法,而每一組施法者讓魔法更加的具現化,量化的方式是兩人電腦的魔力值乘積再乘上兩人之間的距離
(距離的小數點後無條件捨去),而這又被稱為魔法的具現值。

魔法最後的效果量化的結果是基礎值加上具現值和,又被稱為魔法威力,這個值越大,同學們就越容易得救!當然,
如果有施法者施放之後會對整個魔法的具現值有負貢獻,或是沒有人可以配對,也可以選擇不施放,不過也不能轉而去增加基礎值,否則會對整個魔法造成擾動。

至於位於禁區的同學,很遺憾的魔法無須考慮他們的存在,因為他們已經跟這個世界說再見了。

另外,倘若施法者無法構成一個凸多邊形(施法者數量<=2),魔法將無法施展成功,只能無助的迎向悲慘的未來。

現在給你每個同學的位置,已經成為禁區的位置,你有辦法求出魔法威力最大可以是多少嗎?

Input Format

第一行有兩個數字: n 以及m,n 代表學生的數量,m 代表禁區的數量
第二行~第 n+1 行,共 n 行,每行有三個數字:xi ,yi 以及ai,代表每個學生的座標以及魔力值
第 n+2 行~n+m+1 行,共 m 行,每行有兩個數字,xi ,yi,代表每個禁區的座標

Output Format

請輸出一個數字:k,代表魔法威力最高可以達到k
若無法成功施展,請輸出"-1"(不包含雙引號)

Sample Input

Sample Input #1
5 1
0 0 10
2 0 10
0 2 10
2 2 10
1 1 10
1 1

Sample Input #2
1 0
1 1 2147483647

Sample Output

Sample Output #1
400

Sample Output #2
-1

Hints

對於所有測試資料,n<=20,m<=1,000,000,並且保證答案在INT64的範圍內。
並且同一個座標上不會有兩個以上的學生。

Problem Source

原TIOJ1653 / 98建中校內資訊能力競賽(prob4)

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) Output Limit (KiB)
0 3000 65536 262144
1 3000 65536 262144
2 3000 65536 262144
3 3000 65536 262144
4 3000 65536 262144
5 3000 65536 262144
6 3000 65536 262144
7 3000 65536 262144
8 3000 65536 262144
9 3000 65536 262144