TopCoder

呵呵好喔
取出水壺 打開瓶蓋 操課後飲水 500cc 少量多次 喝水 喝水不複誦

User's AC Ratio

100.0% (18/18)

Submission's AC Ratio

86.5% (32/37)

Tags

Description

有一天,好威思思和好威SKYLY比賽誰能比較快讓世界毀滅,結果思思居然輸了。思思一氣之下,居然就不小心得了感冒。

而這時他又不小心將他仔細珍藏的「思思感冒膠囊」打翻了,於是膠囊就散播到了地上。

現在思思面前有 n 顆膠囊( 1 <= n <= 10000 ),每顆膠囊都在一個不同的位置(xi,yi)上( 1 <= xi,yi <= 10000 )。

思思發現他只要吃了 k 顆膠囊( 1 <= k <= n ),感冒就會好了。

因為思思很威,他數藥丸的方式很特別,他第 i 次會拿第 i 個質數顆,並且把它吃掉,而當然如果他感冒已經好了就不會再吃了。
(也就是第一次會拿2顆,第二次會拿3顆,第三次會拿5顆......)

而他第i次移動的單位花費就是i。
(也就是前兩顆移動單位花費是1,3~5顆移動單位花費是2)

某些膠囊之間會有一些關係,也就是要把某個膠囊先吃以後才可以吃另一個。

現在思思剛開始在原點,他想問說在最少花費的情況下,他至少要吃幾顆膠囊,感冒才會好呢?

Input Format

本題只有一筆測試資料。

第一行有兩個整數 n 和 k ,代表有幾顆膠囊和要吃幾顆,感冒才會好。

接下來有 n 行,每行有兩個正整數(xi,yi),表示第 i 個膠囊的位置。

然後接下來有一個數 t ( 1 <= t <= 10000 ),表示有 t 個關係。

接下來 t 行,每行有兩個數 a,b ( 1 <= a,b <= n ),表示要先吃第 a 個膠囊才能吃第 b 個膠囊。

Output Format

請輸出一個數,代表思思至少要吃幾顆膠囊,請輸出到小數點以下6位。

Sample Input 1

1 1
1 0
0

Sample Output 1

1.000000

Hints

這張圖可是海恩威努力了一個晚上的大作耶!

Problem Source

原TIOJ1533

Subtasks

No. Testdata Range Score
1 0 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1