1397 . 高速公路

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

coding_pooh

User's AC Ratio

81.2% (13/16)

Submission's AC Ratio

20.0% (31/155)

Tags

ioicamp ioicamp-2026

Description

LittleCube 成為了 IOIC 王國的首領，他現在要對 IOIC 王國進行都市計畫，預計要興建 $N$ 條高速公路，而王國的領地是一個邊長為 $2 \times 10^ {18}$ 公尺的正方形。為了方便標示位置，LittleCube 把首都定在正方形的中間並設其座標為 $(0, 0)$，所以 IOIC 王國的在地圖標示上左下角為 $(-10^ {18}, -10^ {18})$ 右上角為 $(10^ {18}, 10^ {18})$。

在 LittleCube 的計畫中第 $i$ 條高速公路會經過 $A_ix + B_iy + C_i = 0$ 的地方，當任兩條高速公路相遇時，便需要興建交流道，也就是說假設有 $h$ 條高速公路相遇在同一個點上，那麼那個點上便需要興建 $\binom{h}{2}$ 條交流道。IOIC 王國做事情非常有效率，目前已經興建完所有高速公路了，但經費也所剩無幾，剩下的經費只讓 IOIC 王國興建完 $K$ 條交流道，交流道的興建順序為按照 $X$ 座標排序，若相同再以 $Y$ 座標排序，請你幫忙找出第 $K$ 條完成的交流道的 $X$ 座標是多少？

Input Format

輸入第一行包含兩個正整數 $N$ 和 $K$，分別代表題目所述。

接下來共有 $N$ 行，每行包含三個整數 $A_i, B_i, C_i$。

  • $2\leq N\leq 10^ 5$
  • $1 \leq K \leq \frac{N(N - 1)}{2}$
  • $-10^ 4 \leq A_i, B_i \leq 10^ 4$
  • $-10^ 5 \leq C_i \leq 10^ 5$
  • $(A_i, B_i) \neq (0, 0)$
  • 保證不會有兩條重合的高速公路。

Output Format

輸出第 $K$ 個完成的交流道中的 $X$ 座標，若是交流道總數不到 $K$ 那請輸出 IOIC is so rich!。

輸出的結果與答案相對誤差或絕對誤差在 $10^ {-4}$ 以內就算正確，也就是滿足 $\frac{|A - B|}{\max(1, |B|)} \leq 10^ {-4}$，其中 $A$ 是你的答案，$B$ 是標準答案。

Sample Input 1

5 3
-5 1 3
3 1 1
1 1 1
3 1 5
-2 1 4

Sample Output 1

-0.25000000000000000000

Sample Input 2

6 5
1 1 3
2 1 2
3 1 1
100 1 -96
-1 1 10
-4 1 20

Sample Output 2

1.00000000000000000000

Sample Input 3

5 3
0 1 2
0 1 1
0 1 0
1 0 3
1 0 5

Sample Output 3

-5.00000000000000000000

Sample Input 4

5 8
0 1 2
0 1 1
0 1 0
1 0 3
1 0 5

Sample Output 4

IOIC is so rich!

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~3 範例測資。 0
2 0~3, 20~26, 63~71, 79~83, 94~97 $N \leq 2000$ 13
3 4~5, 31~34, 39~40, 57~62 $1 \leq i \leq N, (A_i, B_i) \in \lbrace(1, 0), (0, 1)\rbrace$ 10
4 16~19, 23~26, 49~62, 68~71, 75~78, 81~83, 90~93, 97 $K \leq 100$ 18
5 6~7, 39~48, 57~62, 96~97 $K \leq 200000$ 且 $(A_i, B_i)$ 至多有兩種可能。 24
6 20~26, 35~38, 67~71, 79~93, 97 $B_i \neq 0$ 5
7 0~97 無特別限制。 30

Testdata and Limits

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