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 wrote:If you use that kind of algo and you got AC, then judge data is incomplete.
What about correct algo ?Krzysztof Duleba wrote: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 wrote:If you use that kind of algo and you got AC, then judge data is incomplete.
Yeah, thanks.Per wrote: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.
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;
}