Maximum Polygon
Practice
3 (4 votes)
Geometry
Ternary search
Hard
Algorithms
Searching algorithm
Convex hull
Problem
65% Success 2415 Attempts 50 Points 5s Time Limit 256MB Memory 1024 KB Max Code

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 \(\frac{The\ area\ of\ the\ convex\ hull}{The\ perimeter\ of\ the\ convex\ hull}\).

Input Format

First line contains two integers \(N,M(2\le M\le N\le 120)\).

Each of the next \(N\) lines contains two integers \(X_i,Y_i(-10^9\le X_i,Y_i\le 10^9)\), 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 \(10^{-6}\) to the answer or subtract \(10^{-6}\) 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. 

Please login to use the editor

You need to be logged in to access the code editor

Loading...

Please wait while we load the editor

Loading...
Results
Custom Input
Run your code to see the output
Submissions
Please login to view your submissions
Similar Problems
No similar problems found