2386 . 第 k 小牙縫

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

abcabcabc
快去寫 TIOJ 2311 > <

User's AC Ratio

56.2% (9/16)

Submission's AC Ratio

31.7% (20/63)

Tags

CKsim 2024-CKsim

Description

瓜瓜在被施巨砲補完牙齒後又遇到了難題。
他覺得自己的牙齒很亂，排列的參差不齊，造成牙齒之間的牙縫有大有小。瓜瓜有 $N$ 顆牙齒，第 $i$ 顆牙齒的座標可以用 $(x_i,y_i)$ 來表示。
特別的是，瓜瓜的牙縫為三顆牙齒圍成的三角形，所以牙縫的大小即為該三角形的面積的兩倍。在經過施巨砲的觀察之後，他發現為了評估瓜瓜的牙齒必須先知道第 $k$ 小的牙縫大小為多少，你能夠找出這個值並再次拯救瓜瓜的牙齒嗎？

Input Format

第一行有兩個正整數 $N,k$ ，意義如題目所述
接下來的 $N $ 行每行有兩個正整數 $x_i,y_i$ ，意義如題目所述
測資保證沒有三點共線

對於所有測試資料：

  • $3 \leq N\leq 800$
  • $1 \leq k\leq \binom{N}{3}$
  • $ |x_i|, |y_i| \leq 10 ^ {6}$

Output Format

輸出第 $k$ 小的牙縫大小。

Sample Input 1

4 3
0 0
-1 -1
1 2
3 1

Sample Output 1

5

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0 範例測資 0
2 0~5 $n\leq 200$ 33
3 0~25 無特別限制 67

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 3000 262144 65536 1 2 3
1 3000 262144 65536 2 3
2 3000 262144 65536 2 3
3 3000 262144 65536 2 3
4 3000 262144 65536 2 3
5 3000 262144 65536 2 3
6 3000 262144 65536 3
7 3000 262144 65536 3
8 3000 262144 65536 3
9 3000 262144 65536 3
10 3000 262144 65536 3
11 3000 262144 65536 3
12 3000 262144 65536 3
13 3000 262144 65536 3
14 3000 262144 65536 3
15 3000 262144 65536 3
16 3000 262144 65536 3
17 3000 262144 65536 3
18 3000 262144 65536 3
19 3000 262144 65536 3
20 3000 262144 65536 3
21 3000 262144 65536 3
22 3000 262144 65536 3
23 3000 262144 65536 3
24 3000 262144 65536 3
25 3000 262144 65536 3
Submit
Back to Top