●POJ 1873 The Fortified Forest

题链：
题解：
计算几何，凸包
枚举被砍的树的集合。求出剩下点的凸包。然后判断即可。
代码：
#include<cmath>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

const int MAXN=16,INF=0x3f3f3f3f;

const double eps=1e-8;

int sign(double x){

	if(fabs(x)<=eps) return 0;

	return x<0?-1:1;

}

struct Point{

	double x,y;

	Point(double _x=0,double _y=0):x(_x),y(_y){}

	void Read(){scanf("%lf%lf",&x,&y);}

}D[MAXN],H[MAXN];

typedef Point Vector;

bool operator < (Point A,Point B){return sign(A.x-B.x)<0||(sign(A.x-B.x)==0&&sign(A.y-B.y)<0);}

bool operator == (Point A,Point B){return sign(A.x-B.x)==0&&sign(A.y-B.y)==0;}

Vector operator - (Point A,Point B){return Vector(A.x-B.x,A.y-B.y);}

double operator ^ (Vector A,Vector B){return A.x*B.y-A.y*B.x;}

double operator * (Vector A,Vector B){return A.x*B.x+A.y*B.y;}

int V[MAXN],N,ansS,ansV,ansN;

double L[MAXN],resL;

double GL(Vector A){//Get_Length

	return sqrt(A*A);

}

int Andrew(int S){

	int hnt=0,k=0,tnt=0;

	static Point tmp[MAXN];

	for(int i=1;i<=N;i++) if(!(S&(1<<(i-1)))) tmp[++tnt]=D[i];

	sort(tmp+1,tmp+tnt+1);

	tnt=unique(tmp+1,tmp+tnt+1)-tmp-1;

	for(int i=1;i<=tnt;i++){

		while(hnt>1&&sign((H[hnt]-H[hnt-1])^(tmp[i]-H[hnt-1]))<=0) hnt--;

		H[++hnt]=tmp[i];

	} k=hnt;

	for(int i=tnt-1;i>=1;i--){

		while(hnt>k&&sign((H[hnt]-H[hnt-1])^(tmp[i]-H[hnt-1]))<=0) hnt--;

		H[++hnt]=tmp[i];

	}

	return hnt;

}

double GCPC(int hnt){//Get_Convex_Polygon_Circumference

	double C=0;

	for(int i=1;i<hnt;i++) C+=GL(H[i+1]-H[i]);

	return C;

}

int main(){

	double C,nowL;

	int nowS,nowV,nowN,Case=0;

	while(scanf("%d",&N)&&N){

		if(N==0) break;

		ansS=(1<<N)-1; ansV=INF; ansN=N; resL=0;

		for(int i=1;i<=N;i++)

			D[i].Read(),scanf("%d%lf",&V[i],&L[i]);

		for(int S=1;S<=(1<<N)-1;S++){

			nowS=S; nowN=0; nowL=0; nowV=0;

			for(int i=1;i<=N;i++) if(S&(1<<(i-1)))

				nowN++,nowV+=V[i],nowL+=L[i];

			C=GCPC(Andrew(S));

			if(sign(nowL-C)<0) continue;

			if(nowV<ansV||(nowV==ansV&&nowN<ansN))

				ansS=nowS,ansV=nowV,ansN=nowN,resL=nowL-C;

		}

		if (Case) puts("");

		printf("Forest %d\n",++Case);

		printf("Cut these trees:");

		for(int i=1;i<=N;i++) if(ansS&(1<<(i-1))) printf(" %d",i);

		printf("\nExtra wood: %.2lf\n",resL);

	}

	return 0;

}
秒客网

●POJ 1873 The Fortified Forest

相关文章
