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

崩溃了,死活检查不出哪里出错了,贴WA程序,大神们帮小菜检查下。。

Posted by Anxier at 2012-03-14 13:03:28 on Problem 1873
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#define eps 1e-8
#define dist(a,b) sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y))
#define cross(a,b,c) (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x)
#define dot(a,b,c) (b.x-a.x)*(c.x-a.x)+(b.y-a.y)*(c.y-a.y)
#define delt(a) fabs(a)<eps?0:a>0?1:-1
#define N 100
#define inf 1234567890000
using namespace std;
struct TPoint
{
    double x,y,vi,hi;
	int id;
}pt[N],st;
int n,m,t,end;
int path[N],mid[N];
double minv,extra;
bool scan()//输入
{
	scanf("%d",&n);
	if(n==0) return 0;
	for(int i=1;i<=n;i++)
	{
		scanf("%lf%lf%lf%lf",&pt[i].x,&pt[i].y,&pt[i].vi,&pt[i].hi);
		pt[i].id=i;
	}
	return 1;
}
bool ncmp(TPoint a,TPoint b)
{
	double s1=cross(st,a,b);
	int d1=delt(s1);
	return d1>0||(d1==0&&dist(st,a)<dist(st,b));
}
bool cmpx(TPoint a,TPoint b)
{
	return a.x<b.x||(a.x==b.x&&a.y<b.y);
}
double graham(TPoint cv[],int np)
{
	int i,k=0,j;
	double alh=0;
	sort(cv,cv+np,cmpx);
	st=cv[0];
	sort(cv,cv+np,ncmp);//内排序
	for(i=2,j=2;i<np;i++)//求凸包
	{
		while(j>1&&cross(cv[j-2],cv[j-1],cv[i])<=0) j--;
		cv[j++]=cv[i];
	}
	cv[j]=cv[0];
	for(i=0;i<j;i++)//求周长
		alh=alh+dist(cv[i],cv[i+1]);
	return alh;
}
void update()
{
	TPoint cv[N];
	int i,j;
	bool vis[N];
	double alv=0,alh=0,alp;
	memset(vis,0,sizeof(vis));
	for(i=0;i<t;i++) vis[mid[i]]=1;
	for(i=1,j=0;i<=n;i++)//记录要砍的树的价值和长度
	{
		if(vis[i]) alv+=pt[i].vi,alh+=pt[i].hi;
		else cv[j++]=pt[i];
	}
	if(j==0||j==1) alp=0;
	else alp=graham(cv,j);//求剩下的树组成凸包的周长
	if(alh-alp>-eps)
	{
		if(alv-minv<-eps)//更新
		{
			minv=alv,extra=alh-alp,m=t;
			for(i=0;i<t;i++) path[i]=mid[i];
		}
	}
}
void dfs(int dep,double val,int id)
{
	if(dep==t)
	{
		update();
		return ;
	}
	for(int i=id;i<=n;i++)
	{
		if(val-minv>-eps) return ;
		mid[dep]=i;
		dfs(dep+1,val+pt[i].vi,i+1);
	}
}
bool cmp(TPoint a,TPoint b)
{
	return a.vi<b.vi||(a.vi==b.vi&&a.hi>b.hi);
}
void solve()
{
	sort(pt,pt+n,cmp);
	minv=inf;
	for(t=1;t<=n;t++)//枚举要砍树的个数
	{
		dfs(0,0,1);
	}
	printf("Forest %d\n",end);
	printf("Cut these trees:");
	bool vis[N];
	int i;
	memset(vis,0,sizeof(vis));
	for(i=0;i<m;i++) vis[pt[path[i]].id]=1;
	for(i=1;i<=n;i++) 
		if(vis[i]) printf(" %d",i);
	puts("");
	printf("Extra wood: %.2f\n",extra);
}
int main()
{
	end=1;
    while(scan())
    {
		puts("");
		solve();
		end++;
    }
    return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator