Maximum Polygon

3

4 votes
Geometry, Ternary search, Hard, Algorithms, Searching algorithm, Convex Hull
Problem

Given N points on plane, the N points forms a convex polygon. You need to find M points among them, then we calculate the convex hull of the M points.

You need to maximize The area of the convex hullThe perimeter of the convex hull.

Input Format

First line contains two integers N,M(2MN120).

Each of the next N lines contains two integers Xi,Yi(109Xi,Yi109), represent a point.

It's guaranteed no two points coincide.

Output Format

One float number, represent the answer, round to 4 decimal digits. It's guaranteed the output will not change if we add 106 to the answer or subtract 106 from the answer.

Note : The statement for this problem has been updated. We are rejudging all submissions, please check announcement on contest page for detailed issue. 

Sample Input
6 4
1 0
2 1
2 2
1 3
0 1
0 2
Sample Output
0.4109
Time Limit: 5
Memory Limit: 256
Source Limit:
Explanation

The sample is in the above graph. Area=3,Perimeter7.300563.

Editor Image

?