TopCoder

Caido
主唱太拼命了

User's AC Ratio

100.0% (1/1)

Submission's AC Ratio

100.0% (1/1)

Tags

Description

在唯一神 olmrgcsi 的領土上,人類種 rgnerdplayer 和神靈種 baluteshih 正在車輪戰。

這次的遊戲是競程大地遊戲。遊戲地圖是一個可以被視為二維平面的沙漠。唯一神 olmrgcsi 在沙漠上的 $n$ 個位置放置了據點,每一個據點都有一道難度堪比 Atcoder Grand Contest G 題難度的競程題目。第 $i$ 個據點的位置是 $(x_i, y_i)$,解開據點的題目就可以佔領該據點。地圖上還有 $m$ 條直線道路,每一條道路連結兩個據點。每一條道路在兩端點以外不會路過其他的據點,任兩條道路也不會在端點以外的地方相交。rgnerdplayer 會先選擇一個出發點,接著 baluteshih 會選擇一個不同的出發點。兩位玩家都要透過道路到達 $n$ 個據點並 AC 據點中的問題,AC 的數量多者贏得勝利,如果數量相同則是 rgnerdplayer 勝利。

但是眾所周知,Atcoder Grand Contest 對神靈種比 div3 對人類種還要簡單,因此這 $n$ 道題目 baluteshih 都可以在兩秒內做出來。沒有勝算的 rgnerdplayer 在危急時刻想起了唯一神 olmrgcsi 曾經給他一些魔法石,每一顆魔法石可以用來炸掉任何一條道路。由於可能還有派上用場的機會,rgnerdplayer 想要用最少的魔法石,讓 baluteshih 無法移動到所有的據點。由於 rgnerdplayer 有先選擇起點的權利,他就可以贏得這場比賽了,即使這 $n$ 道題目有可能會花他一輩子的時間。

請問 rgnerdplayer 最少需要多少魔法石才能夠取勝?

TL:DR:以圖論的術語來說,你有一個平面圖且平面鑲嵌已知,最少要刪掉幾條邊才能使圖不是連通的?

Definitions and Hints:

  1. 平面圖 (planar graph) 的定義是存在一種平面鑲嵌 (plane graph/planar embedding) 的圖。平面鑲嵌的定義是把圖的點和邊畫在平面上的一種方式,使得任兩條邊不會在端點以外相交。簡單 (simple) 圖的定義是沒有重邊或自環的圖。特別的,本題給定的平面鑲嵌中每一條邊都是一條直線。

  2. 依據歐拉公式 $v - e + f = 2$ 可以證明簡單連通平面圖有 $e \leq 3v - 6$,其中 $v$ 是點的數量、$e$ 是邊的數量、$f$ 是平面被劃分成的區域的數量(包含外側延伸到無限大的那個區域)。

Input Format

輸入第一行兩個個正整數 $n, m$,分別代表地圖上據點的數量,以及地圖上道路的數量。

接著 $n$ 行每一行有兩個正整數 $x_i, y_i$,代表第 $i$ 個據點的位置。

接著 $m$ 行每一行有兩個正整數行 $u_i, v_i$,代表編號 $u_i, v_i$ 的據點中間連了一條直線的道路。

  • $1 \leq n \leq 10^ 5$
  • $0 \leq m \leq 3n - 6$
  • $0 \leq x_i, y_i \leq 10^ 9$
  • $1 \leq u_i, v_i \leq n$
  • 保證沒有兩個據點在同一個位置,但可能有三點共線
  • 保證輸入是一個平面圖

Output Format

輸出一行包含一個整數,代表問題的答案。

Sample Input 1

6 0
128 912
438972 11
12506 12390
5680 123098
23598 2817
9015 981

Sample Output 1

0

Sample Input 2

4 6
30 199
36 0
777 187
100 190
1 2
2 3
4 1
4 3
4 2
3 1

Sample Output 2

3

Sample Input 3

9 21
0 0
49 100
100 0
50 50
40 45
40 30
51 20
60 30
60 44
1 2
2 3
3 1
4 5
5 6
7 6
8 7
8 9
9 4
4 6
8 6
4 8
1 5
1 6
1 7
9 3
7 3
8 3
2 4
2 5
2 9

Sample Output 3

4

Hints

Problem Source

IOICamp 2023 Day5 pI

Subtasks

No. Testdata Range Constraints Score
1 0~2 範例測資。 0
2 3~22 $n \leq 9$。 5
3 3~50 $n \leq 60$。 20
4 51~55 答案只會是 $0$ 或 $1$。 2
5 51~89 答案小於等於 $2$。 5
6 51~113 答案小於等於 $3$。 13
7 3~113 無特別限制。 55

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 262144 65536 1
1 1000 262144 65536 1
2 1000 262144 65536 1
3 1000 262144 65536 2 3 7
4 1000 262144 65536 2 3 7
5 1000 262144 65536 2 3 7
6 1000 262144 65536 2 3 7
7 1000 262144 65536 2 3 7
8 1000 262144 65536 2 3 7
9 1000 262144 65536 2 3 7
10 1000 262144 65536 2 3 7
11 1000 262144 65536 2 3 7
12 1000 262144 65536 2 3 7
13 1000 262144 65536 2 3 7
14 1000 262144 65536 2 3 7
15 1000 262144 65536 2 3 7
16 1000 262144 65536 2 3 7
17 1000 262144 65536 2 3 7
18 1000 262144 65536 2 3 7
19 1000 262144 65536 2 3 7
20 1000 262144 65536 2 3 7
21 1000 262144 65536 2 3 7
22 1000 262144 65536 2 3 7
23 1000 262144 65536 3 7
24 1000 262144 65536 3 7
25 1000 262144 65536 3 7
26 1000 262144 65536 3 7
27 1000 262144 65536 3 7
28 1000 262144 65536 3 7
29 1000 262144 65536 3 7
30 1000 262144 65536 3 7
31 1000 262144 65536 3 7
32 1000 262144 65536 3 7
33 1000 262144 65536 3 7
34 1000 262144 65536 3 7
35 1000 262144 65536 3 7
36 1000 262144 65536 3 7
37 1000 262144 65536 3 7
38 1000 262144 65536 3 7
39 1000 262144 65536 3 7
40 1000 262144 65536 3 7
41 1000 262144 65536 3 7
42 1000 262144 65536 3 7
43 1000 262144 65536 3 7
44 1000 262144 65536 3 7
45 1000 262144 65536 3 7
46 1000 262144 65536 3 7
47 1000 262144 65536 3 7
48 1000 262144 65536 3 7
49 1000 262144 65536 3 7
50 1000 262144 65536 3 7
51 1000 262144 65536 4 5 6 7
52 1000 262144 65536 4 5 6 7
53 1000 262144 65536 4 5 6 7
54 1000 262144 65536 4 5 6 7
55 1000 262144 65536 4 5 6 7
56 1000 262144 65536 5 6 7
57 1000 262144 65536 5 6 7
58 1000 262144 65536 5 6 7
59 1000 262144 65536 5 6 7
60 1000 262144 65536 5 6 7
61 1000 262144 65536 5 6 7
62 1000 262144 65536 5 6 7
63 1000 262144 65536 5 6 7
64 1000 262144 65536 5 6 7
65 1000 262144 65536 5 6 7
66 1000 262144 65536 5 6 7
67 1000 262144 65536 5 6 7
68 1000 262144 65536 5 6 7
69 1000 262144 65536 5 6 7
70 1000 262144 65536 5 6 7
71 1000 262144 65536 5 6 7
72 1000 262144 65536 5 6 7
73 1000 262144 65536 5 6 7
74 1000 262144 65536 5 6 7
75 1000 262144 65536 5 6 7
76 1000 262144 65536 5 6 7
77 1000 262144 65536 5 6 7
78 1000 262144 65536 5 6 7
79 1000 262144 65536 5 6 7
80 1000 262144 65536 5 6 7
81 1000 262144 65536 5 6 7
82 1000 262144 65536 5 6 7
83 1000 262144 65536 5 6 7
84 1000 262144 65536 5 6 7
85 1000 262144 65536 5 6 7
86 1000 262144 65536 5 6 7
87 1000 262144 65536 5 6 7
88 1000 262144 65536 5 6 7
89 1000 262144 65536 5 6 7
90 1000 262144 65536 6 7
91 1000 262144 65536 6 7
92 1000 262144 65536 6 7
93 1000 262144 65536 6 7
94 1000 262144 65536 6 7
95 1000 262144 65536 6 7
96 1000 262144 65536 6 7
97 1000 262144 65536 6 7
98 1000 262144 65536 6 7
99 1000 262144 65536 6 7
100 1000 262144 65536 6 7
101 1000 262144 65536 6 7
102 1000 262144 65536 6 7
103 1000 262144 65536 6 7
104 1000 262144 65536 6 7
105 1000 262144 65536 6 7
106 1000 262144 65536 6 7
107 1000 262144 65536 6 7
108 1000 262144 65536 6 7
109 1000 262144 65536 6 7
110 1000 262144 65536 6 7
111 1000 262144 65536 6 7
112 1000 262144 65536 6 7
113 1000 262144 65536 6 7