思路:
二进制枚举一下要删哪些点
求个凸包, 算一下贡献
- //By SiriusRen
- #include <cmath>
- #include <cstdio>
- #include <algorithm>
- using namespace std;
- #define eps 1e-9
- int n,cases,top,tot,k,rem,ansrem,ans;
- double length,tempdis,wei,answei,remwei;
- struct Tree{double x,y,v,l;}tr[25],point[25],tubao[25];
- bool operator<(Tree a,Tree b){if(abs(a.x-b.x)<eps)return a.y<b.y;return a.x<b.x;}
- double operator*(Tree a,Tree b){return a.x*b.y-a.y*b.x;}
- Tree operator-(Tree a,Tree b){Tree c;c.x=a.x-b.x;c.y=a.y-b.y;return c;}
- double dis(Tree a){return sqrt(a.x*a.x+a.y*a.y);}
- double cross(Tree a,Tree b,Tree c){return (a-c)*(b-c);}
- int main(){
- while(scanf("%d",&n)&&n){
- answei=1000000;
- for(int i=0;i<n;i++)scanf("%lf%lf%lf%lf",&tr[i].x,&tr[i].y,&tr[i].v,&tr[i].l);
- for(int i=0;i<(1<<n);i++){
- length=tot=top=rem=tempdis=wei=0;
- for(int j=0;j<n;j++){
- if(i&(1<<j))point[++tot]=tr[j],rem++;
- else length+=tr[j].l,wei+=tr[j].v;
- }
- sort(point+1,point+1+tot);
- for(int j=1;j<=tot;j++){
- while(top>1&&cross(tubao[top],point[j],tubao[top-1])<-eps)top--;
- tubao[++top]=point[j];
- }k=top;
- for(int j=tot-1;j>=1;j--){
- while(top>k&&cross(tubao[top],point[j],tubao[top-1])<-eps)top--;
- tubao[++top]=point[j];
- }
- for(int j=1;j<top;j++)tempdis+=dis(tubao[j]-tubao[j+1]);
- if(tempdis<length){
- if(wei<answei)answei=wei,ansrem=rem,ans=i,remwei=length-tempdis;
- else if(wei==answei&&rem<ansrem)ansrem=rem,ans=i,remwei=length-tempdis;
- }
- }
- printf("Forest %d\nCut these trees:",++cases);
- for(int j=0;j<n;j++)if(!(ans&(1<<j)))printf("%d",j+1);
- printf("\nExtra wood: %.2lf\n\n",remwei);
- }
- }
来源: http://www.bubuko.com/infodetail-2704146.html