Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
大过年的还在纠结这道题目,求大神帮忙看看。。。我找了个AC的程序,随机了n组数据,两个程序跑出的结果是一样的,但是始终是wa。。。o(╯□╰)o 这题有没有什么trick? 附wa的代码 #include <iostream> #include <math.h> using namespace std; struct node { int id; double x,y; double v; double l; }; node mm[20]; int ans,ansnum,ansv; double ansleft; bool vis[20]; double cal(node x) { return sqrt(x.x*x.x+x.y*x.y); } double cal2(node aa,node bb) { return sqrt((aa.x-bb.x)*(aa.x-bb.x)+(aa.y-bb.y)*(aa.y-bb.y)); } double tubao(int x,int n) { int i; node temp; int sid; temp.id=-1; temp.x=999999999; temp.y=999999999; for(i=0;i<n;i++) { if(vis[i])continue; if(temp.x==mm[i].x&&temp.y>mm[i].y) { temp=mm[i]; } if(temp.x>mm[i].x) { temp=mm[i]; } } if(temp.id==-1)return 0; sid=temp.id; node last,nn; last.x=0; last.y=-1; int tt; double sum; sum=0; do { double cos,tempcos; cos=-2; for(i=0;i<n;i++) { if(i==temp.id)continue; if(vis[i])continue; nn.x=mm[i].x-temp.x; nn.y=mm[i].y-temp.y; tempcos=(last.x*nn.x+last.y*nn.y)/(cal(last)*cal(nn)); if(tempcos>cos) { cos=tempcos; tt=i; } } if(tt<0||tt>=n)return 0; sum+=cal2(temp,mm[tt]); last.x=mm[tt].x-temp.x; last.y=mm[tt].y-temp.y; temp=mm[tt]; }while(temp.id!=sid); return sum; } void work(int x,int n) { int i; memset(vis,0,sizeof(vis)); int num; double val; double sum; sum=0; val=0; num=0; for(i=0;i<n;i++) { if(x&(1<<i)) { vis[i]=1; sum+=mm[i].l; num++; val+=mm[i].v; } } if(val==ansv&&ansnum<num)return ; if(val>ansv)return ; double len; len=tubao(x,n); if(len>sum)return ; if(val==ansv&&ansnum==num) { if(sum-len>ansleft) { ans=x; ansnum=num; ansleft=sum-len; ansv=val; } } else { ans=x; ansnum=num; ansleft=sum-len; ansv=val; } } void output(int x) { int cnt; cnt=0; while(x) { cnt++; if(x%2)printf(" %d",cnt); x/=2; } } int main () { // freopen("in.txt","r",stdin); // freopen("out1.txt","w",stdout); int n,i; int cnt; cnt=0; while(scanf("%d",&n)!=EOF&&n) { cnt++; for(i=0;i<n;i++) { mm[i].id=i; scanf("%lf%lf%lf%lf",&mm[i].x,&mm[i].y,&mm[i].v,&mm[i].l); } ansnum=20; ansv=INT_MAX; for(i=1;i<(1<<n);i++) { work(i,n); } printf("Forest %d\n",cnt); printf("Cut these trees:"); output(ans); printf("\nExtra wood: %.2lf\n\n",ansleft); } return 0; } Followed by:
Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator