Moderator: Board moderators

This problem seems simple. However, my brute force solution got WA. As the problem does not say explicitly, I assume the input can be in real numbers. My algorithm is as follows:

1. initialize result[] to 0 and read in all trees
2. for each tree i, find the minimum distance amongst all other trees and store it in minDistance[i]
3. if minDistance[i] < 10, add 1 to the corresponding bin, ie, ++result[(int) minDistance[i]]
4. print out the result array

Did I miss something or misunderstand anything? Would anyone please provide a set of input/output for my testing - I can only find one in the forum and my program got it right. Here is my code:
Code: Select all
`#include <cstdio>#include <cmath>#include <climits>using namespace std;#ifndef DBL_MAXconst double DBL_MAX = 1.7976931348623158e+308;#endifstruct Point{  double x, y, z;};Point tree[5000];int treeNum = 0;int result[10] = {0};double minDistance[5000];int main(){  for (int i = 0; i < 5000; ++i) {    minDistance[i] = DBL_MAX;  }  while (true) {    Point & p = tree[treeNum];    scanf("%lf %lf %lf", &p.x, &p.y, &p.z);    if (p.x == 0 && p.y == 0 && p.z == 0) break;    ++treeNum;  }  for (int i = 0; i < treeNum; ++i) {    for (int j = 0; j < treeNum; ++j) {      if (i == j) continue;      double xDist = tree[j].x - tree[i].x;      double yDist = tree[j].y - tree[i].y;      double zDist = tree[j].z - tree[i].z;      double distSquare = xDist * xDist + yDist * yDist + zDist * zDist;      double dist = sqrt(distSquare);      if (dist < minDistance[i]) {        minDistance[i] = dist;      }    }    if (minDistance[i] < 10) {      ++result[(int) minDistance[i]];    }  }  for (int i = 0; i < 10; ++i) {    printf("%4d", result[i]);  }  putchar('\n');}`
rickyliu
New poster

Posts: 30
Joined: Thu Sep 28, 2006 7:16 am

I got AC but I did not feel happy. I managed to find the input and output of the judge used. I have verified this by just sending the output line and got AC. Then, I verified with my program's output and found no differences. Since my compiler (GCC 3.4.2 mingw-special) changed the variable treeNum to 0 after reading 5,000 input lines (it worked when I added -O2 to optimize the code - weird and possibly compiler's bug), I started to suspect this problem might be caused by the compiler used by the judge.

To verify my claim, I rewrote the above C++ program so that it could be compiled using a C compiler. I submitted this C program and got AC. Then, I submitted the same program but asked the judge to use C++ compiler. I got WA this time!

Could someone please explain to me why the results were different using different compilers? Here is the rewriting code:

Code: Select all
`#include <stdio.h>#include <math.h>#include <limits.h>#ifndef DBL_MAXconst double DBL_MAX = 1.7976931348623158e+308;#endifstruct Point{  double x, y, z;};struct Point tree[5000];int treeNum = 0;int result[10] = {0};double minDistance[5000];int main(){  int i, j;  double xDist, yDist, zDist, distSquare, dist;  for (i = 0; i < 5000; ++i) {    minDistance[i] = DBL_MAX;  }  while (1) {    scanf("%lf %lf %lf", &tree[treeNum].x, &tree[treeNum].y, &tree[treeNum].z);    if (tree[treeNum].x == 0 && tree[treeNum].y == 0 && tree[treeNum].z == 0) break;    ++treeNum;  }  for (i = 0; i < treeNum; ++i) {    for (j = 0; j < treeNum; ++j) {      if (i == j) continue;      xDist = tree[j].x - tree[i].x;      yDist = tree[j].y - tree[i].y;      zDist = tree[j].z - tree[i].z;      distSquare = xDist * xDist + yDist * yDist + zDist * zDist;      dist = sqrt(distSquare);      if (dist < minDistance[i]) {        minDistance[i] = dist;      }    }    if (minDistance[i] < 10) {      ++result[(int) minDistance[i]];    }  }  for (i = 0; i < 10; ++i) {    printf("%4d", result[i]);  }  putchar('\n');  return 0;}`
rickyliu
New poster

Posts: 30
Joined: Thu Sep 28, 2006 7:16 am

Sorry that I made a very stupid mistake in my code.
SA, please delete this post. Thanks.
rickyliu
New poster

Posts: 30
Joined: Thu Sep 28, 2006 7:16 am

I renew this topic. I got Runtime Error. Could sb explain what I have wrong ?

Code: Select all
`#include<iostream>#include<vector>#include<set>#include<cmath>#include<algorithm>#include<iomanip>#define rep(x,n) for (int x = 0; x < n; x++)#define pb push_backusing namespace std;struct tr{ double x,y,z;};struct cmp{ bool operator() (tr a, tr b) {  if (a.x == b.x)  {    if (a.y == b.y)    {    if (a.z == b.z) return true; else return (a.z < b.z);    }    else return (a.y < b.y);  } else return (a.x < b.x); }};set <tr,cmp> D;int main(){  tr a,b,d;vector <int> zaj; zaj.resize(10,0); do {  cin >> a.x >> a.y >> a.z; D.insert(a); } while (! (a.x == 0 && a.y == 0 && a.z == 0)); D.erase(D.begin()); for (set<tr,cmp>::iterator it = D.begin(); it != D.end(); it++) {  double d1 = -1,d2 = -1; b = *(it); // cout <<"------------------ " <<b.x << " " << b.y << " "  <<b.z << "\n";  if (it != D.begin())  {   --it; d = *(it); ++it;   d1 = sqrt((b.x-d.x)*(b.x-d.x) + (b.y-d.y)*(b.y-d.y) + (b.z-d.z)*(b.z-d.z));  // cout << "D1" <<d1 << "\n";  }  set<tr,cmp>::iterator itk = D.end(); itk--;  if (it != itk)  {   ++it; d = *(it); --it;   d2 = sqrt((b.x-d.x)*(b.x-d.x) + (b.y-d.y)*(b.y-d.y) + (b.z-d.z)*(b.z-d.z));  // cout << "d2 " << d2 << "\n";  }  if (d1 != -1 && d2 != -1)  {//cout << "czc " << int(d1) << " " << int(d2) << "\n";   int g = min(int(d1),int(d2)); if (g < 10)++zaj[g];  // cout << "better " << "\n";  }  else if (d1 == -1 && d2 < 10) { ++zaj[int(d2)]; } else if (d1 < 10) {++zaj[int(d1)];  }  //cout <<"d1 " << d1 << "\n";  //cout << "d2 " << d2 << "\n"; } rep(x,10) {  cout << setw(4) << zaj[x] << " "; } return 0;}`
mic122
New poster

Posts: 6
Joined: Mon Apr 09, 2012 1:01 pm

Input:
Code: Select all
`1 1 1255 255 2550 0 0`

AC Output
Code: Select all
`   0   0   0   0   0   0   0   0   0   0`
brianfry713
Guru

Posts: 1742
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA