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

为什么这两份代码一份AC,一份WA(注意两份代码只有第9行处声明不同)

Posted by peter1341 at 2014-09-17 22:11:29 on Problem 2728
/*********AC*********/
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;

int n;

const int MAXN = 1010;
#define INF 10000000
const double eps = 1e-6;

struct NODE
{
    double x,y,z;
}nodes[MAXN];

int vis[MAXN];
double dis[MAXN];
int pre[MAXN];

double distance(NODE a, NODE b)
{
	return sqrt((a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y));
}

double prime(double r)
{
	memset(vis, 0, sizeof(vis));
	for (int i = 1; i <= n; i++)
	{
		dis[i] = fabs(nodes[1].z - nodes[i].z) - distance(nodes[1], nodes[i])*r;
		pre[i] = 1;
	}
	int pos = 1;
	vis[1] = 1;
	dis[1] = 0;
	double cost=0, len = 0;
	for (int i = 1; i < n; i++)
	{
		double MIN = INF;
		for (int j = 1; j <= n; j++)
			if (vis[j] == 0 && MIN > dis[j])
			{
			MIN = dis[j];
			pos = j;
			}
		vis[pos] = 1;
		cost += fabs(nodes[pre[pos]].z - nodes[pos].z);
		len += distance(nodes[pre[pos]], nodes[pos]);
		for (int j = 1; j <= n; j++)
		{
			double val = fabs(nodes[pos].z - nodes[j].z) - distance(nodes[pos], nodes[j])*r;
			if (vis[j] == 0 && dis[j] > val)
			{
				dis[j] = val;
				pre[j] = pos;
			}
		}
	}
	return cost / len;
}

int main()
{
	while (scanf("%d", &n) == 1 && n)
	{
		for (int i = 1; i <= n; i++)
			scanf("%lf%lf%lf", &nodes[i].x, &nodes[i].y, &nodes[i].z);

		double a = 0, b = 0;
		while (1)
		{
			b = prime(a);
			if (fabs(b - a) < 1e-4)  break;
			a = b;
		}
		printf("%.3f\n", b);
	}
	return 0;
}
/*********WA***********/
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;

int n;

const int MAXN = 1010;
const double INF = 100000.0;
const double eps = 1e-6;

struct NODE
{
    double x,y,z;
}nodes[MAXN];

int vis[MAXN];
double dis[MAXN];
int pre[MAXN];

double distance(NODE a, NODE b)
{
	return sqrt((a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y));
}

double prime(double r)
{
	memset(vis, 0, sizeof(vis));
	for (int i = 1; i <= n; i++)
	{
		dis[i] = fabs(nodes[1].z - nodes[i].z) - distance(nodes[1], nodes[i])*r;
		pre[i] = 1;
	}
	int pos = 1;
	vis[1] = 1;
	dis[1] = 0;
	double cost=0, len = 0;
	for (int i = 1; i < n; i++)
	{
		double MIN = INF;
		for (int j = 1; j <= n; j++)
			if (vis[j] == 0 && MIN > dis[j])
			{
			MIN = dis[j];
			pos = j;
			}
		vis[pos] = 1;
		cost += fabs(nodes[pre[pos]].z - nodes[pos].z);
		len += distance(nodes[pre[pos]], nodes[pos]);
		for (int j = 1; j <= n; j++)
		{
			double val = fabs(nodes[pos].z - nodes[j].z) - distance(nodes[pos], nodes[j])*r;
			if (vis[j] == 0 && dis[j] > val)
			{
				dis[j] = val;
				pre[j] = pos;
			}
		}
	}
	return cost / len;
}

int main()
{
	while (scanf("%d", &n) == 1 && n)
	{
		for (int i = 1; i <= n; i++)
			scanf("%lf%lf%lf", &nodes[i].x, &nodes[i].y, &nodes[i].z);

		double a = 0, b = 0;
		while (1)
		{
			b = prime(a);
			if (fabs(b - a) < 1e-4)  break;
			a = b;
		}
		printf("%.3f\n", b);
	}
	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