Drawing a Mountain Range
Time limit2sMemory limit128 MB
Given n polyline points, choose K interior points (plus both endpoints) to form an approximating polyline that minimizes the total area between it and the original mountain outline.
- Level
Medium7 of 10
- Topics
- Dynamic programming, Geometry, Math
- Solved
- No attempts yet
Problem
A mountain range is described by N points. All x-coordinates are distinct, and the points are given in increasing order of x-coordinate. Connecting adjacent points in order forms the original shape of the mountain range.
When the shape is complicated, we want to approximate it using only the two endpoints and K points chosen between them, for a total of K+2 points. The chosen points are also connected in increasing order of x-coordinate.
The goal is to minimize the total area of the parts where the original mountain range and the approximated mountain range differ. Compute that minimum total area.
Input
The first line contains two integers n and K. (3 <= n <= 100, 0 <= K <= n-2)
Each of the next n lines contains the x-coordinate and y-coordinate of one point of the mountain range. The points are given in increasing order of x-coordinate, and every coordinate is a natural number not greater than 500.
Output
Print the minimum possible total area of the differing parts. An absolute or relative error of at most 10^-6 is accepted.