还没打完, 先放着
- #include<bits/stdc++.h>
- using namespace std;
- const int N=20;
- #define eps 1e-8
- #define inf 0x3f3f3f3f
- int sgn(double x){
- if(fabs(x)<eps) return 0;
- if(x<0) return -1;
- return 1;
- }
- struct Point{
- double x,y,l;
- int v;
- Point operator - (const Point& b)const{
- return (Point){x-b.x,y-b.y};
- }
- double operator ^ (const Point& b)const{
- return x*b.y-b.x*y;
- }
- }p[N],a[N],p0;
- int sta[N];
- int n;
- bool vis[N];
- double dist(Point a,Point b){
- return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
- }
- bool cmp(Point a,Point b){
- if(atan2(a.y-p0.y,a.x-p0.x)!=atan2(b.y-p0.y,b.x-p0.x)){
- return (atan2(a.y-p0.y,a.x-p0.x)<atan2(b.y-p0.y,b.x-p0.x));
- }
- return a.x<b.x;
- }
- double graham(int cnt){
- if(cnt<2) return 0;
- if(cnt==2) return dist(a[1],a[2]);
- p0=a[1];
- int k=1;
- for(int i=2;i<=cnt;++i){
- if((p0.y> a[i].y) || (p0.y==a[i].y && p0.x>a[i].x)){
- p0=a[i];
- k=i;
- }
- }
- a[k]=a[1];
- a[1]=p0;
- sort(a+2,a+1+cnt,cmp);
- sta[0]=1; sta[1]=2;
- int top=1;
- for(int i=3;i<=n;++i){
- while(top>0&&((a[i]-a[sta[top-1]])^(a[sta[top]]-a[sta[top-1]])) <= 0) --top;
- sta[++top]=i;
- }
- double ans=0;
- for(int i=0;i<top;++i) ans+=dist(a[sta[i]],a[sta[i+1]]);
- ans+=dist(a[sta[0]],a[sta[top]]);
- return ans;
- }
- int ans[N];
- int main(){
- int n;
- int cas=0;
- while(~scanf("%d",&n) && n){
- for(int i=0;i<n;++i) scanf("%lf %lf %d %lf",&p[i].x,&p[i].y,&p[i].v,&p[i].l);
- int ansv=inf,ansn=inf,anslef;
- for(int i=0;i<(1<<n);++i){
- memset(vis,0,sizeof(vis));
- int temv=0,temn=0;
- double teml=0;
- int cnt=0;
- for(int j=0;j<n;++j){
- if((1<<j) & i){
- vis[j]=1;
- ++temn;
- temv+=p[j].v;
- teml+=p[j].l;
- }
- else a[++cnt]=p[j];
- }
- if(temv> ansv || (temv==ansv && temn> ansn)) continue;
- double used=graham(cnt);
- if(used <= teml){
- ansv=temv;
- anslef=teml-used;
- ansn=0;
- for(int u=1;u<=n;++u) if(vis[u]) ans[++ansn]=u;
- }
- }
- printf("Forest %d\n",++cas);
- printf("Cut these trees:");
- for(int i=1;i<=ansn;++i) printf("%d",ans[i]);
- printf("\n");
- printf("Extra wood: %.2lf\n",ansv);
- puts("");
- }
- }
- View Code
来源: http://www.bubuko.com/infodetail-3209200.html