LINK

题意：给出点集，每个点有个价值v和长度l,问把其中几个点取掉，用这几个点的长度能把剩下的点围住，要求剩下的点价值和最大，拿掉的点最少且剩余长度最长。

思路：1999WF中的水题。考虑到其点的数量最多只有15个，那么可以使用暴力枚举所有取点情况，二进制压缩状态，预处理出该状态下的价值，同时记录该状态拥有的点，并按价值排序。按价值枚举状态，并对拥有的这些点求凸包，check是否合法，找到一组跳出即可。然而POJ似乎没有SPJ，同样的代码POJ会超时，UVA60ms，可以在常数上优化，不预处理，实时判价值最大值，不使用结构体等

/** @Date    : 2017-07-16 14:48:08  * @FileName: POJ 1873 凸包.cpp  * @Platform: Windows  * @Author  : Lweleth (SoungEarlf@gmail.com)  * @Link    : https://github.com/  * @Version : $Id$  */#include <stdio.h>#include <iostream>#include <string.h>#include <algorithm>#include <utility>#include <vector>#include <map>#include <set>#include <string>#include <stack>#include <queue>#include <math.h>//#include <bits/stdc++.h>#define LL long long#define PII pair<int ,int>#define MP(x, y) make_pair((x),(y))#define fi first#define se second#define PB(x) push_back((x))#define MMG(x) memset((x), -1,sizeof(x))#define MMF(x) memset((x),0,sizeof(x))#define MMI(x) memset((x), INF, sizeof(x))using namespace std;const int INF = 0x3f3f3f3f;const int N = 1e5+20;const double eps = 1e-8;struct point{	double x, y;	point(){}	point(double _x, double _y){x = _x, y = _y;}	point operator -(const point &b) const	{		return point(x - b.x, y - b.y);	}	double operator *(const point &b) const 	{		return x * b.x + y * b.y;	}	double operator ^(const point &b) const	{		return x * b.y - y * b.x;	}};double xmult(point p1, point p2, point p0)  {      return (p1 - p0) ^ (p2 - p0);  }  double distc(point a, point b){	return sqrt((double)((b - a) * (b - a)));}int sign(double x){	if(fabs(x) < eps)		return 0;	if(x < 0)		return -1;	else 		return 1;}////////////point pt[50];int v[50], l[50];struct yuu{	point p[50];	int val;	int cnt;	int len;	int sta;	double cst;	void init(){cnt = len = val = cst = 0;}}tt[1 << 16];point stk[50];/*int cmpA(point a, point b)//以p[0]基准 极角序排序{	int t = xmult(a, b, p[0]);	if(t > 0)		return 1;	if(t == 0)		return distc(a, p[0]) < distc(b, p[0]);	if(t < 0)		return 0;}*/int cmpB(yuu a, yuu b)//预处理用{	if(a.val == b.val)		return a.cnt < b.cnt;	return a.val < b.val;}int cmpC(point a, point b)//水平序排序{	return sign(a.x - b.x) < 0 || (sign(a.x - b.x) == 0 && sign(a.y - b.y) < 0);}/*void grahamS(){	while(!s.empty())		s.pop();	for(int i = 0; i < min(n, 2); i++)		s.push(i);	int t = 1;	for(int i = 2; i < n; i++)	{		while(s.size() > 1)		{			int p2 = s.top();			s.pop();			int p1 = s.top();			if(xmult(p[p1], p[p2], p[i]) > 0)			{				s.push(p2);				break;			} 		}		s.push(i);	}}*/int graham(int st)//水平序{	sort(tt[st].p, tt[st].p + tt[st].cnt, cmpC);	int top = 0;	for(int i = 0; i < tt[st].cnt; i++)	{		while(top >= 2 && sign(xmult(stk[top - 2], stk[top - 1], tt[st].p[i])) <= 0)			top--;		stk[top++] = tt[st].p[i];	}	int tmp = top;	for(int i = tt[st].cnt - 2; i >= 0; i--)	{		while(top > tmp && sign(xmult(stk[top - 2],stk[top - 1] ,tt[st].p[i] )) <= 0)			top--;		stk[top++] = tt[st].p[i];	}	if(tt[st].cnt > 1)		top--;	return top;}int check(int st){	int ma = graham(st);	double ans = 0;	stk[ma] = stk[0];	for(int i = 0; i < ma; i++)		ans += distc(stk[i + 1], stk[i]);	tt[st].cst = ans;	if(sign(tt[st].len - ans) < 0)		return 0;	return 1;}int main(){	int n;	int cc = 0;	while(~scanf("%d", &n) && n)	{		if(cc)			printf("\n");		cc++;		double x, y;		for(int i = 0; i < n; i++)		{			scanf("%lf%lf%d%d", &x, &y, v + i, l + i);			pt[i] = point(x, y);		}		int c = 0;		for(int st = 0; st < (1 << n); st++)//预处理		{			tt[st].sta = st;			tt[st].init();			c = 0;			for(int i = 0; i < n; i++)			{				if(st & (1 << i))					tt[st].len += l[i], tt[st].val += v[i];				else 					tt[st].p[c++] = pt[i];			}			tt[st].cnt = c;		}		sort(tt, tt + (1 << n), cmpB);		//////		for(int st = 0; st < (1 << n); st++)//遍历		{			if(check(st))			{				printf("Forest %d\n", cc);				printf("Cut these trees:");				for(int i = 0; i < n; i++)				{					if(tt[st].sta & (1 << i))						printf(" %d", i + 1);				}				printf("\nExtra wood: %.2lf\n", ((double)tt[st].len - tt[st].cst + eps));				break;			}		}	}    return 0;}

Uva5211／POJ1873 The Fortified Forest 凸包