同和创作矩阵 › ›博文归档› 技术博文归档 › 查看内容

22122_Convexhullagain

2022-5-16 18:21| 发布者: Hocassian| 查看: 21| 评论: 0|原作者: 肇庆学院ACM合集

摘要:

C:\Users\Administrator\Downloads\2019-10-12-10-14-5-89506127678700-Problem List-采集的数据-后羿采集器.html

Pro.ID

22122

Title

Convex hull again

Title链接

http://10.20.2.8/oj/exercise/problem?problem_id=22122

AC

Submit

Ratio

时间&空间限制

Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 131072/65536 K (Java/Others)

描述

Maxwell is a naughty boy.

One day, he fouled the white and clean wall with ink. Since his mother will come back home soon, Maxwell wanted to find a white convex polygon to cover these ink drops. Could you tell him the minimal area of the convex polygon which can cover all the ink drops?

Now, given the coordinates of these ink drops, you will answer the minimal area of the convex polygon that can cover all the ink drops.

输入

The first line of the input is a positive integer T. T is the number of the test cases followed. The first line of each test case is a positive integer N (0 < N <= 10⁵). N is the number of the ink drops. After that, N lines are followed. The i-th line contains two integers X, and 7, (0 <= Xi, Yi < 20000) which tell you the coordinate of the i-th ink drops. There may be one or more spaces between these integers.

输出

Description

Maxwell is a naughty boy.

Now, given the coordinates of these ink drops, you will answer the minimal area of the convex polygon that can cover all the ink drops.

Input

Output

The output of the program should consist of one line of output for each test case. The output of each test case only contains the minimal area of the convex polygon. The area is a real number that has one digit after the decimal point. No redundant spaces are needed.

Sample Input

0 0

1 0

0 1

1 1

0 0

0 1

Sample Output

1.0

0.0

Source

GDCPC 2004