935 . 披薩慶祝大會

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

餘切
$\huge\text{owoovo is 8}$

User's AC Ratio

100.0% (12/12)

Submission's AC Ratio

100.0% (13/13)

Tags

ioicamp ioicamp-2025

Description

跑完馬拉松後，因為你昨天寫的程式幫克勞蒂亞和他的學生們很大的忙，她們決定請你吃披薩。

她們買了一片很奇怪的披薩，這個披薩是一個凸多邊形，可以把它放在座標平面上。

克勞蒂亞讓你選若干個披薩的頂點，她們會切出這些頂點所形成的凸包的披薩送你。

但是因為你昨天胃食道逆流，所以你想讓切出來的面積最小。請問你最少要吃面積多大的披薩？

當然，你不能讓你選的頂點所形成的凸包退化成一條線或是一個點，因為這樣暗示你完全不想吃，會傷克勞蒂亞的心。

Input Format

輸入第一行為一個正整數 $n$ ，代表披薩的頂點數。

接下來 $n$ 行，每行有兩個數字 $x_i,y_i$ ，代表將披薩放在座標平面上時第 $i$ 個頂點的座標。

  • $3\leq n\leq 3 \times 10^ 4$
  • $-10^ 7\leq x_i,y_i\leq10^ 7$
  • 保證所給的 $n$ 個座標點兩兩相異，任三點不共線，且形成一個凸包，且給點的順序按照逆時針方向排序。

Output Format

輸出一個正整數 $2A$ ，代表你選的最小凸包面積乘以 2。

Sample Input 1

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

Sample Output 1

7

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0 範例測資 0
2 0~5 $3\leq n\leq 20$ 8
3 0~10 $3\leq n\leq 1000$ 31
4 0~15 無額外限制 61

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 1048576 65536 1 2 3 4
1 1000 1048576 65536 2 3 4
2 1000 1048576 65536 2 3 4
3 1000 1048576 65536 2 3 4
4 1000 1048576 65536 2 3 4
5 1000 1048576 65536 2 3 4
6 1000 1048576 65536 3 4
7 1000 1048576 65536 3 4
8 1000 1048576 65536 3 4
9 1000 1048576 65536 3 4
10 1000 1048576 65536 3 4
11 1000 1048576 65536 4
12 1000 1048576 65536 4
13 1000 1048576 65536 4
14 1000 1048576 65536 4
15 1000 1048576 65536 4
Submit
Back to Top