Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

大过年的还在纠结这道题目，求大神帮忙看看。。。

Posted by huxinjie at 2011-02-02 18:24:45 on Problem 1873
```我找了个AC的程序，随机了n组数据，两个程序跑出的结果是一样的，但是始终是wa。。。o(╯□╰)o

#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: