10750 - Beautiful Points

[Shahriar Nirjon]

I solved this by first sorting by x, then searched O(n*n) in worst case, but some optimization led to a solution of 0:00.213 sec. My question is, Is all the solutions takin time < 0.2 sec are using wrong Algo, or using some different Algo. In the former case I want Rejudgement & in the later case I want to learn.

[Krzysztof Duleba]

If you use that kind of algo and you got AC, then judge data is incomplete.

Don't be so surprised. Big cases are often random generated, so one can achieve good time making some assumptions that usually, but not always, hold.

[rotoZOOM]

If you use that kind of algo and you got AC, then judge data is incomplete.

Don't be so surprised. Big cases are often random generated, so one can achieve good time making some assumptions that usually, but not always, hold.

What about correct algo ?
Does every people (who got AC in online contest) use wrong algo ?

[Per]

I used a (hopefully) correct implementation of the O(n log n) divide-and-conquer algorithm, got AC in the contest.

As Krzysztof said, you can read about it in CLR. Or it shouldn't be too hard to find a page describing it, if you search for closest pair.

[rotoZOOM]

I used a (hopefully) correct implementation of the O(n log n) divide-and-conquer algorithm, got AC in the contest.

As Krzysztof said, you can read about it in CLR. Or it shouldn't be too hard to find a page describing it, if you search for closest pair.

Yeah, thanks.
I tried to find CLR but its size 11Mb in djvu format, so I can't download it whole.
But I'll search for closest pair.

[ovidiu]

Please tell me what is wrong in the next code, or tell me a test case for which the code produce wrong results.

Code: Select all

#include <iostream>
#include <iomanip>
#include <math.h>

using namespace std;

#ifndef ONLINE_JUDGE
  #include <fstream>
  #define cin fi
  #define cout fo
  fstream fi("BeautifulPoints.in",ios::in);
  fstream fo("BeautifulPoints.out",ios::out);
#endif
#define lim 20000

struct point {
  int x, y;
};

point p[10001], cp1, cp2;
int i, j, n, nc, t, dx, dy, pd, mind;

int compare (const void* p1, const void* p2) {
  return ((point*)p1)->x-((point*)p2)->x;
}
int main() {
  cin >> nc;
  for (t = 1; t <= nc; t++) {
    cin >> n;
    for (i = 1; i <= n; i++)
      cin >> p[i].x >> p[i].y;
    qsort(p+1, n, sizeof(point), compare);
    mind = lim*lim;
    for (i = 1; i <= n-1; i++)
      for (j = i+1; j <= n; j++) {
        dx = p[j].x-p[i].x;
        if (dx*dx >= mind)
          break;
        else {
          dy = p[j].y-p[i].y;
          pd = dx*dx+dy*dy;
          if (pd < mind) {
            mind = pd; cp1 = p[i]; cp2 = p[j];
          }
        }
      }
    cout << fixed << setprecision(3) << (float)(cp1.x+cp2.x)/2 << ' ';
    cout << fixed << setprecision(3) << (float)(cp1.y+cp2.y)/2;
    if (t < nc)
      cout << endl << endl;
  }
  cout << endl;
  return 0;
}

[MAK]

I tried this problem with a line sweep algo, but I keep getting WA. The same approach passed in 10245. Can anyone suggest some tricky test cases?

Thanks in advance,
MAK