0

I am trying to solve the following problem:

Farmer John has acquired a set of N (2 <= N <= 2,000) touchy cows who are conveniently numbered 1..N. They really hate being too close to other cows. A lot.

FJ has recorded the integer X_i,Y_i coordinates of every cow i (1 <= X_i <= 100,000; 1 <= Y_i <= 100,000).

Among all those cows, exactly two of them are closest together. FJ would like to spread them out a bit. Determine which two are closest together and print their cow id numbers (i) in numerical order.

                10 | . . . . . . . 3 . . . . .
                 9 | . 1 . . 2 . . . . . . . .
                 8 | . . . . . . . . . . . . .
                 7 | . . . . . . . . . . 4 . .
                 6 | . . . . . . 9 . . . . . .
                 5 | . 8 . . . . . . . . . . .
                 4 | . . . . . 7 . . . . . . .
                 3 | . . . . . . . . . 5 . . .
                 2 | . . . . . . . . . . . . .
                 1 | . . . . 6 . . . . . . . .
                 0 ---------------------------
                                       1 1 1 1
                   0 1 2 3 4 5 6 7 8 9 0 1 2 3

Quick visual inspection shows that cows 7 and 9 are closest together (the distance separating them is sqrt(11+22) = sqrt(5), so the output would be '7 9' on a single line (without quotes, of course).

Below is my coded attempt to solve the problem:

using namespace std;

int main() {
   int n; cin >> n;
   long long xcord[n],ycord[n];

   for (int i=0; i<n; i++) {
       cin >> xcord[i];
       cin >> ycord[i];
   }

   long long shortest = 9999999999999;
   int a=-1, b=-1;
   for (int i=0; i<n; i++) {
       for (int j=i+1; j<=n; j++) {
           long long curDist = (xcord[i]-xcord[j])*(xcord[i]-xcord[j]) + (ycord[i]-ycord[j])*(ycord[i]-ycord[j]);
           // cout << curDist << " ";
           if (curDist < shortest) {
               shortest = curDist;
               a=i+1, b=j+1;
           }
       }
   }
   cout << a << " " << b << endl;

}

Here is the test case I am running: 25 24804 7918 98983 95075 10819 48641 84481 33476 56724 20854 83193 17014 72997 5394 69263 33045 26810 75288 85442 47243 81678 82129 84199 35206 68212 77035 62113 87896 49538 1375 145 90953 58175 62546 73175 5853 7789 37961 18883 49418 78257 90342 2048 64282 49057 95081 89406 47329 9778 68104

When I run the test case using my code, I get the correct answer, 7 18. I am running the code using VSCode. When I try running the code using replit, I get a completely different answer despite the test case being the same and when I try running the same test case over and over in replit, the program returns differing answers. Do you know why I am getting this error? Thanks a lot!

rioV8
  • 24,506
  • 3
  • 32
  • 49
Pigeon01
  • 25
  • 5
  • 1
    ever tried a debugger yourself to find the problem in your code – rioV8 Apr 18 '22 at 23:26
  • 2
    Differing behavior usually means there is some undefined behavior in your code. `for (int j=i+1; j<=n; j++) {` looks like it could cause UB as it appears to be an off by 1 error. `j<=n` is often wrong and is definitely wrong here. Your arrays have valid range of 0 .. n-1 but you access `xcord[j]` which is `xcord[n]` on the last iteration or one element past the end of the xcord array. – drescherjm Apr 18 '22 at 23:27
  • 1
    Standard C++ [does not have variable-length arrays](https://stackoverflow.com/questions/1887097/why-arent-variable-length-arrays-part-of-the-c-standard) (VLAs). Use `std::vector` instead. – heap underrun Apr 18 '22 at 23:30
  • Thanks. I fixed the error by changing the j<=n to j – Pigeon01 Apr 18 '22 at 23:32

1 Answers1

3

Right here you go out of bounds on your array

 for (int j = i + 1; j <= n; j++) 
 -----------------------^

that should be

for (int j = i + 1; j < n; j++)

now gives 7 18

pm100
  • 48,078
  • 23
  • 82
  • 145