Just Cover It

Time Limit: 6000/3000MS (Java/Others) Memory Limit: 12000/6000KB (Java/Others)

Problem Description

Give you N points on an plane,the coordinates of each point are integers。

Can you cover all the N points using no more than M triangles ?

 If you can,can you tell me the minimum area of the  maximum area of all the M triangles?

You should note that each vertice of a triangle should be one of the N points,

Covering means that all points should be within the triangles or on the edge of any triangle.

Input

The first line is an integer T(1<=T<=100) ,the number of test cases;

For each test case,

N (3<=N<=18),the number of points,M,meaning tthe maximum number of trianlges

The following N lines is the coordinates

all numbers will between 0 and 29999.

Output

A decimal number ,the minimum area descripts above or -1.0 if covering is failed.

Sample Input

1
3 1
0 0
0 1
1 0

Sample Output

0.5

Hint

保留一位小数,三角形不能退化(点重合),这题极限数据很少

Source

dream

Manager

Information
Solved Number16
Submit Number193
Problem Tags
binary search
sortings
No tag edit access
温馨提示:AC后可以编辑标签哦. ^-^
Login
LoginCancel