| ||||||||||
| 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,一份WA(注意两份代码只有第9行处声明不同)/*********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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator