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