#include <iostream>
#include <stdio.h>
#include <cmath>
#include <algorithm>
using namespace std;

int B, N;

const double PI = 3.141592654;
const double INF_D = 1e10;
struct pt{
	int x,y;
}points[110];

pt origin;

double K[110];
double dp[60][110][110];

double k(pt p){
	int x = p.x, y = p.y;
	if(y == 0 && x > 0) return 0;
	if(y == 0) return PI;
	if(x == 0 && y > 0) return 0.5*PI;
	if(x == 0) return 1.5*PI;
	double ans = atan2(y+0.0,x+0.0);
	if(ans < 0) ans += 2*PI;
	return ans;
}

bool compare(int p1, int p2){
	return K[p1] < K[p2];
}

int sign(pt p1, pt p2, pt p3){
	int get = p1.x*p2.y + p2.x*p3.y + p3.x*p1.y - p1.y*p2.x - p2.y*p3.x - p3.y*p1.x;
	if(get > 0) return 1;
	return -1;
}

int intvLen(int a, int b){
	if(a <= b) return b-a+1;
	else return b+(N-1)-a+1;
}

bool neimian(pt p1, pt p2, pt p3){
	int sign1 = sign(p1, p2, origin);
	int sign2 = sign(p1, p2, p3);
	if(sign1 * sign2 == 1) return 0;
	return 1;
}

double mianji(pt p1, pt p2){
	return 0.5 * abs(0.0 + p1.x*p2.y-p1.y*p2.x);
}

int main() {
	origin.x = 0, origin.y = 0;
	while(1){
		scanf("%d%d", &B, &N);
		if(B == 0 && N == 0) return B+N;
		int x,y;
		scanf("%d%d", &x, &y);
		for(int i = 0; i < N-1; i++){
			int X, Y;
			scanf("%d%d", &X, &Y);
			X -= x, Y -= y;
			points[i].x = X, points[i].y = Y;
		}
		int order[110];
		for(int i = 0; i < N-1; i++) order[i] = i;
		for(int i = 0; i < N-1; i++) K[i] = k(points[i]);
		sort(order, order+N-1, compare);
		double mj[110][110];
		for(int startP = 0; startP < N-1; startP++){
			int dygd = (startP + 1)%(N-1);
			int dians[110], dianNum = 2;
			dians[0] = startP, dians[1] = dygd;
			int curP;
			mj[startP][dygd] = 0.5*abs(0.0+points[order[startP]].x*points[order[dygd]].y-points[order[startP]].y*points[order[dygd]].x);
			for(curP = (dygd+1)%(N-1); ; curP = (curP+1)%(N-1)){
				double cha = K[order[curP]] - K[order[startP]];
				if(cha > PI+1e-8 || (cha < 0 && cha > -PI+1e-8)){
					break;
				}
				if(!neimian(points[order[dians[dianNum-2]]], points[order[dians[dianNum-1]]], points[order[curP]])){
					dians[dianNum] = curP;
					mj[startP][curP] = mj[startP][dians[dianNum-1]] + mianji(points[order[dians[dianNum-1]]], points[order[curP]]);
					dianNum++;
				}
				else{
					//二分
					int l = 0, u = dianNum - 2;
					while(l != u){
						int m = (l+u)/2;
						if(neimian(points[order[dians[m]]], points[order[dians[m+1]]], points[order[curP]])){
							u = m;
						}
						else{
							l = m+1;
						}
					}
					dians[l+1] = curP;
					mj[startP][curP] = mj[startP][dians[l]] + mianji(points[order[dians[l]]], points[order[curP]]);
					dianNum = l+2;
				}
			}
			for(int bknP = curP; bknP != startP; bknP = (bknP+1)%(N-1)){
				mj[startP][bknP] = INF_D;
			}
		}
		for(int i = 0; i < N-1; i++){
			for(int j = 0; j < N-1; j++){
				if(i == j) continue;
				dp[1][i][j] = mj[i][j];
			}
		}
		for(int b = 2; b <= B; b++){
			for(int i = 0; i < N-1; i++){
				for(int j = 0; j < N-1; j++){
					int intvL = intvLen(i, j);
					if(i == j || intvL < 2*b || (b==B && intvL != N-1)) continue;
					double mn = INF_D;
					for(int iL = 2; iL <= intvL - 2*b + 2; iL++){
						int end = (i+iL-1)%(N-1), stt = (end+1)%(N-1);
						double tmp = mj[i][end] + dp[b-1][stt][j];
						if(tmp < mn) mn = tmp;
					}
					dp[b][i][j] = mn;
				}
			}
		}
		double ans = INF_D;
		for(int i = 0; i < N-1; i++){
			double tempAns = dp[B][i][(i+N-2)%(N-1)];
			if(tempAns < ans) ans = tempAns;
		}
		printf("%.2lf\n", ans);
	}
	return 0;
}

• 说下思路吧 (515) KatrineYang 2016-08-30 12:08:15