2425.cpp

这是哈尔滨工业大学acmOJ的源代码

/* This Code is Submitted by wywcgs for Problem 2425 on 2006-12-06 at 20:01:24 */
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

const int N = 128;
const double NINF = -1e20, INF = 1e20;
const double eps = 1e-5;

class Point {
public:
	double x, y;
	Point() {}
	Point(double cx, double cy) : x(cx), y(cy) {}
	void make() { scanf("%lf %lf", &x, &y); }
	bool operator <(const Point& p) const { return x+eps < p.x; }
};

double ydvalue(Point& a, Point& b, Point& c) { return a.y+(b.y-a.y)/(b.x-a.x)*(c.x-a.x)-c.y; }

double opt[N][N], disb[N][N];

int main()
{
	Point p[N];
	int n, m;

	while(scanf("%d %d", &n, &m) != EOF && n != 0) {
		for(int i = 0; i < n; i++) p[i].make();
		int cvx[N], cn = 0;
		cvx[cn++] = 0;
		for(int i = 0, j; i < n-1; i = j) {
			double v = NINF;
			for(int k = i+1; k < n; k++) {
				double tanv = (p[k].y-p[i].y)/(p[k].x-p[i].x);
				if(v < tanv+eps) { j = k; v = tanv; }
			}
			cvx[cn++] = j;
		}
		for(int i = 0; i < cn; i++)
			for(int j = 0; j <= m; j++)
				opt[i][j] = INF;
		for(int i = 1; i < cn; i++)
			for(int k = i+1; k < cn; k++) {
				double a1 = (p[cvx[i-1]].y-p[cvx[i]].y)/(p[cvx[i-1]].x-p[cvx[i]].x),
					a2 = (p[cvx[k-1]].y-p[cvx[k]].y)/(p[cvx[k-1]].x-p[cvx[k]].x),
					k1 = (p[cvx[i]].y-a1*p[cvx[i]].x), k2 = (p[cvx[k]].y-a2*p[cvx[k]].x);
				double ix = -(k1-k2)/(a1-a2);
				int pos = lower_bound(p, p+n, Point(ix, 0))-p;
				disb[i][k] = 0;
				for(int j = cvx[i]; j < cvx[k]; j++)
					if(j >= pos) disb[i][k] >?= ydvalue(p[cvx[k-1]], p[cvx[k]], p[j]);
					else disb[i][k] >?= ydvalue(p[cvx[i-1]], p[cvx[i]], p[j]);
			}
		for(int i = 1; i < cn; i++) {
			opt[i-1][1] = 0;
			for(int j = 0; j < cvx[i]; j++)
				opt[i-1][1] >?= ydvalue(p[cvx[i-1]], p[cvx[i]], p[j]);
		}
		for(int j = 2; j <= m; j++)
			for(int i = 1; i < cn; i++)
				for(int k = i+1; k < cn; k++)
					opt[k-1][j] <?= max(opt[i-1][j-1], disb[i][k]);
		double best = INF;
		for(int i = 1; i < cn; i++) {
			double r = opt[i-1][m];
			for(int j = cvx[i]; j < n; j++) r >?= ydvalue(p[cvx[i-1]], p[cvx[i]], p[j]);
			best <?= r;
		}
		printf("%.3lf\n", best);
	}

	return 0;
}