10245 - The Closest Pair Problem

[Observer]

I follow all your instructions, but I'm still getting WA!!!!!!

Why??? Plz help!!!


P.S. I'm using Pascal

[Dominik Michniewski]

I think, that's not important which language you use Observer ....
I think, that you have a small mistake in your code - maybe precision error ? Of course if you use correct algorithm
I use algorithm which have O(nlogn) time complexity and I get 0.7 sec time ... tryto post your code to me - maybe I can help you but I don;t write in pascal, so I can find mistakes (possible mistakes) - I wrote in pascal, but I don;t have compiler of it

Best regards
DM

[Larry]

How do you get O( n log n )? (Without finding the Delauncy triangulation?)

PS: My original problem was that I expected the points to be all integers, for some odd reason..

[UFP2161]

Hint: Sort the points by x,y, and use early exits when you iterate through them.

[Riyad]

i am having trouble in the prob 10245 . i tried the brute force O(n^2) instead of the O(n*log(n)) . but i am getting RTE . My array of structure for storing the points are big enough i guess ,,10008.plizzzzzzzzzzz help me this.
here is my code :

[c]
#include<stdio.h>
#include<math.h>

struct p{

unsigned long int x , y ;
};

struct p obj[10008];
int index;


unsigned long int distance(struct p a , struct p b ){

unsigned long long int d,sx,sy;

sx=((a.x-b.x)*(a.x-b.x));

sy=((a.y-b.y)*(a.y-b.y));

d=sx+sy;



if(d>100000000ULL)
return 100000000UL;
return (unsigned long int)d;

}

unsigned long int check(){

unsigned long int result,k ;
int i , j ;

result = 100000000UL;

for(i=0;i<index-1;i++){

for(j=i+1;j<index;j++){

k=distance(obj,obj[j]);

if(k<result)result=k;

else if(k>result)
continue;
}
}

return result ;

}

int main(){

int set;
unsigned long int ax,ay;

//freopen("input.txt","r",stdin);

while(scanf("%d",&set)==1){

if(set==0)break;

if(set==1){
scanf("%lu %lu",&ax,&ay);
printf("INFINITY\n");
}

else{

index=0;

while(set>0){

scanf("%lu %lu",&ax,&ay);

obj[index].x=ax;
obj[index].y=ay;
index++;
set--;
}

ax=check();



if(ax>=100000000UL)
printf("INFINITY\n");
else
printf("%.4lf\n",sqrt(ax));


}

}

return 0;
}[/c]

Thanx in advance
Bye
Riyad

[Chameleon]

I must have forfeited 10 TLEs and 5 WAs on this question ... apparently the coordinates are doubles, not ints. It does not say anything either way in the question, but the examples are misleading.

[Frostina]

Would you please give some hint ?
I use sqrt() only once, but I still got TLE ... Q Q"

[Pavl0]

J get WA by brutr force, first j sort all points by x
next check all n^2 , witch some optimalization by x
end get WA plese give mi some sample input/output
or find bug im my prog
meybe problem is in rounding ??

[c]

#include<stdio.h>
#include<stdlib.h>
#include<math.h>

struct point
{
long double x,y;
}
pty[10010];

int compare(const void *a,const void *b)
{

if(0<((*(struct point*)a).x-(*(struct point*)b).x))return 1;
return -1;
}


main()
{
int ile,i,j;
long double rec,odl;
long double d1,d2;
float a,b,c,d1_,d2_;
char ch[25];
while(1)
{
scanf("%d",&ile);
if(ile==0)break;
rec=100000000;
for(i=0;i!=ile;i++)
{
scanf("%Lf %Lf",&pty.x,&pty.y);
if(i!=0)
{
d1=pty.x-pty[i-1].x;
d2=pty.y-pty[i-1].y;
odl=(d1*d1)+(d2*d2);
if(rec>odl)rec=odl;

}
}
if(ile==1){printf("INFINITY\n"); continue;}

qsort(pty,ile,sizeof(point),compare);

for(i=0;i!=ile;i++)
for(j=i;j!=ile;j++)
{
if(j==i)continue;
d1=pty[j].x-pty.x;
if((d1*d1)>rec){/*printf("OPT %d %d\n",i,j);*/break;}
d2=pty[j].y-pty.y;

odl=(d1*d1)+(d2*d2);
if(rec>odl)rec=odl;

}

if(rec==100000000)printf("INFINITY\n");
else {


c=rec;
c=sqrt(c);

for(i=0;i!=20;i++)ch=0;


sprintf(ch,"%.4f",c);
sscanf(ch,"%f",&b);

a=b;
a=a+0.0001;



d1_=c-a;
d2_=c-b;


if(d1_<0)d1_=d1_*-1;
if(d2_<0)d2_=d2_*-1;

if(d1_>d2_)printf("%.4f\n",b);
else printf("%.4f\n",a);


}


}


}[/c]

[cypressx]

I Don`t get it . I don`t like publishing code , but in this case I can`t avoid it .. :

#include <stdio.h>
#include <vector>
#include <math.h>
#define FOR(i,n) for(int i=0;i<n;i++)
#define REP(i,f,t) for(int i=f;i<=t;i++)

double abss(double x) { return x > 0 ? x : -x; }
double dist(double x,double y,double x1,double y1) {
return sqrt(abss((x-x1)*(x-x1) + (y-y1)*(y-y1)));
}
int main() {
int n;
for(;;) {
scanf("%d",&n);
if(n == 0) return 0;
std::vector<std::pair<int,int> > v;
int x,y;
FOR(i,n) {
scanf("%d %d",&x,&y);
v.push_back(std::make_pair(x,y));
}
double mindist = 10000;
double tmp;
FOR(i,n) {
REP(j,i+1,n-1) {
if((tmp=dist(v.first,v.second,v[j].first,v[j].second)) < mindist) {
mindist = tmp;
}
}
}
if(n == 1) {
printf("INFINITY\n");
}
else
if(mindist == 10000) {
printf("INFINITY\n");
}
else printf("%.4f\n",mindist);
}
return 0;
}

I do not know how I get output limit exceeded ? when I have if`s and elses at the end , and they seem clear to me . Any help is appreciated

[diac_paul]

I get the same : output limit. I really don't know why but it seems like the test 5 has the case n=1 in witch the problem dosen't says what to print. If i don't print anything (if n=1) i still get output limit. What can be the problem?
pls help.

[zhenh]

Here are some simple test cases:

3
0 0
10000 10000
20000 20000
5
0 2
6 67
43 71
39 107
189 140
6
-100 1
-100 -1
0 0
0 0
100 1
100 -1
1
10000 10000
6
-100 1
-100 2
0 0
0 1
2 1
3 5
5
1 0
0 2
35 7
1000 1000
1000 1001
12
1 0
0 2
35 7
77 92
1000 1000
1000 1001
10000 -4000
10005 2573
10007 8763
10007 8763
10020 0
10029 89
1
0 0
0

And your program gives:

0.0000
0.0000
0.0000
INFINITY
0.0000
0.0000
0.0000
INFINITY

Half of them are ,obviously , incorrect.

And your code has so poor a readability...
That makes it hard to be debugged.

NOTE: Manzoor must have some trickier inputs, since I am still
receiving WAs...

[zhenh]

Code: Select all

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define MAX_PTS 10005
#define MAX_DIST 10000.0
#define EPSILON 1e-12

typedef struct point
{
 double x;
 double y;
 int X_index;
 int Y_index;
}point;

int X[MAX_PTS];
int Y[MAX_PTS];
point pts[MAX_PTS];
int n_pts;

int cmpX(const void *a, const void *b);
int cmpY(const void *a, const void *b);
double dist(point *p1, point *p2);
double closest(int *Xp, int *Yp, int np);
double lfabs(double x);
double lfmin(double a, double b);
int    imin(int a, int b);

int main()
{
 int i;
 double min_d;

 while (scanf("%d", &n_pts)==1 && n_pts > 0)
 {
  for (i = 0;i < n_pts;i ++)
  {
   scanf("%lf%lf", &pts[i].x, &pts[i].y);
   X[i] = i;
   Y[i] = i;
  }
  qsort(X, n_pts, sizeof(int), cmpX);
  qsort(Y, n_pts, sizeof(int), cmpY);
  for (i = 0;i < n_pts;i ++)
  {
   pts[X[i]].X_index = i;
   /*
   printf("X[%d] = (%.2lf,%.2lf)\n",pts[X[i]].X_index,pts[X[i]].x,
     pts[X[i]].y);
     */
  }
  min_d = closest(X, Y, n_pts);
  if (min_d < MAX_DIST)
  {
   /* no round off */
   min_d *= 10000;
   min_d = (double)((long)min_d);
   min_d /= 10000;
   printf("%.4lf\n", min_d);
  }
  else
  {
   printf("INFINITY\n");
  }
 }
 return 0;
}

int cmpX(const void *a, const void *b)
{ /* sort points according to x coordinate */
 int ia,ib;
 ia = *(int *)a;
 ib = *(int *)b;
 if (pts[ia].x < pts[ib].x)
  return -1;
 if (pts[ia].x > pts[ib].x)
  return 1;
 return 0;
}

int cmpY(const void *a, const void *b)
{ /* sort points according to y coordinate */
 int ia,ib;
 ia = *(int *)a;
 ib = *(int *)b;
 if (pts[ia].y < pts[ib].y)
  return -1;
 if (pts[ia].y > pts[ib].y)
  return 1;
 return 0;
}

double dist(point *p1, point *p2)
{
 if (p1->x == p2->x)
  return lfabs(p1->y-p2->y);
 if (p1->y == p2->y)
  return lfabs(p1->x-p2->x);
 if (lfabs(p1->x-p2->y) >= MAX_DIST || lfabs(p1->y-p2->y) >= MAX_DIST)
  return MAX_DIST;
 return sqrt((p1->x-p2->x)*(p1->x-p2->x)+(p1->y-p2->y)*(p1->y-p2->y));
}

double lfmin(double a, double b)
{
 if (a < b)
  return a;
 return b;
}

int imin(int a, int b)
{
 if (a < b)
  return a;
 return b;
}

double lfabs(double x)
{
 if (x < 0)
  return -x;
 return x;
}

double closest(int *Xp, int *Yp, int np)
{
 double min_d;
 double lrD;
 int i,j,k;
 int mid;
 int Xl[MAX_PTS/2];
 int Yl[MAX_PTS/2];
 int Xr[MAX_PTS/2];
 int Yr[MAX_PTS/2];
 int yp;

 if (np == 1)
  return MAX_DIST;
 if (np == 2)
 {
  min_d = dist(&pts[Xp[0]],&pts[Xp[1]]);
  /*
  printf("np = %d, min_d = %.4lf\n",np, min_d);
  printf("np2 : (%.2lf,%.2lf)\n", pts[Xp[0]].x, pts[Xp[0]].y);
  printf("np2 : (%.2lf,%.2lf)\n", pts[Xp[1]].x, pts[Xp[1]].y);
  */
  return min_d;
 }
 if (np == 3)
 {
  min_d = dist(&pts[Xp[0]],&pts[Xp[1]]);
  min_d = lfmin(min_d, dist(&pts[Xp[1]],&pts[Xp[2]]));
  min_d = lfmin(min_d, dist(&pts[Xp[0]],&pts[Xp[2]]));
  /*
  printf("np = %d, min_d = %.4lf\n", np, min_d);
  */
  return min_d;
 }
 if (np%2 == 0)
  mid = np/2-1;
 else
  mid = np/2;
 /* divide */
 for (i = 0;i <= mid;i ++)
 {
  Xl[i] = Xp[i];
 }
 for (i = mid+1;i < np;i ++)
 {
  Xr[i-mid-1] = Xp[i];
 }
 j = 0;
 k = 0;
 for (i = 0;i < np;i ++)
 {
  if (pts[Yp[i]].x <= pts[Xp[mid]].x)
   Yl[j++] = Yp[i];
  else
   Yr[k++] = Yp[i];
 }
 /* conquer */
 lrD = MAX_DIST;
 /*
 printf("conquer(np=%d): len(Xl)=%d len(Yl)=%d\n",np,mid+1,j);
 printf("conquer(np=%d): len(Xr)=%d len(Yr)=%d\n",np,np/2,k);
 */
 lrD = closest(Xl, Yl, mid+1);
 /*
 printf("after conquering left part, lrD = %.4lf\n", lrD);
 */
 lrD = lfmin(lrD, closest(Xr, Yr, np/2));
 /*
 printf("right part conquered, lrD = %.4lf\n", lrD);
 */
 /* combine */
 yp = 0;
 for (i = 0;i < np;i ++)
 {
  if (lfabs(pts[Yp[i]].x-pts[Xp[mid]].x) < lrD)
   Yl[yp++] = Yp[i];
 }
 /*
 printf("points within 2*[%.4lf] stripe of (%.2lf,%.2lf)[%d]:\n",
  lrD, pts[Xp[mid]].x, pts[Xp[mid]].y, mid);
 for (i = 0;i < yp;i ++)
  printf("#%d : (%.2lf,%.2lf)\n", i, pts[Yl[i]].x, pts[Yl[i]].y);
  */
 min_d = lrD;
 for (j = 0;j <= yp-2;j ++)
 {
  k = j+1;
  while (k <= yp-1 && pts[Yl[k]].y - pts[Yl[j]].y < lrD+EPSILON)
  {
   min_d = lfmin(min_d, dist(&pts[Yl[k]],&pts[Yl[j]]));
   k++;
  }
 }
 return min_d;
}

I have tried 20 times, all got WA.
I cannot think of any reason....
Any idea?

[jdmetz]

/* no round off */
min_d *= 10000;
min_d = (double)((long)min_d);
min_d /= 10000;
printf("%.4lf\n", min_d);

Why do you assume no round off? If fixing the bug below doesn't work, I'd try changing this assumption.

if (lfabs(p1->x-p2->y) >= MAX_DIST || lfabs(p1->y-p2->y) >= MAX_DIST)

I think you want p1->x-p2->x (not p2->y).

[tan_Yui]

Hi, everyone!
I solved this problem just now, CPU time : about 0.7 sec.
The site "Methods to Solve" gives me good advices.

First submission, I got Output Limit Exceeded.
This was caused by the type of the set of coordinates.
I'd read the the coordinates by 'int', but this was wrong in some case.
After changed 'int' to 'double', I could aboid Output Limit Exceeded.

And rjhadley's hint was very nice for me.
I also missed case N=1 -> output 'INFINITY'.

Finally, I prepared a test case.
This may help you.

Input :

3
0 0
10000 10000
20000 20000
5
0 2
6 67
43 71
39 107
189 140
1
0 0
3
1 1
1 1
1 1
30
5253 2675
1436 1023
8447 1510
4610 406
538 4362
6299 2192
585 3791
5674 8538
9614 6466
6246 2506
915 4726
4660 411
5722 624
8857 6201
5093 7510
2588 2060
4949 4693
9181 5893
5443 7492
8136 329
4655 4812
9319 8815
4572 1012
3707 6556
1656 3150
520 4729
7037 8659
5251 1017
8617 1775
5644 573
30
647 806
998 945
395 611
641 923
423 625
490 684
327 571
767 821
792 294
963 157
366 960
208 350
142 205
767 467
850 596
251 331
888 270
376 359
153 466
87 930
106 321
702 85
644 860
161 895
228 999
163 471
410 580
43 770
394 800
199 819
30
184 125
253 37
364 470
155 331
233 341
18 322
337 207
237 357
249 51
146 470
308 441
24 227
155 367
375 475
319 119
283 113
329 298
428 258
134 387
58 82
273 263
260 256
177 112
242 410
112 297
318 496
433 204
28 376
341 81
204 217
30
134 154
151 212
48 129
204 61
203 130
58 226
191 41
68 225
234 90
135 146
30 135
177 14
148 24
65 33
150 86
56 52
226 69
215 74
243 178
184 73
60 10
65 113
6 55
20 168
175 212
222 104
16 39
79 201
187 126
133 80
100
283 211
947 1581
1915 1178
571 1753
1392 1459
1138 554
1399 1440
1000 1960
1686 1702
1383 229
1724 524
716 569
617 337
1429 1934
812 768
1119 1643
288 341
253 1456
694 29
1704 1286
97 1503
409 1076
1683 940
327 1185
283 1255
49 285
684 693
682 1869
380 1251
471 538
401 1802
1754 57
1339 772
1181 553
1297 1691
797 655
557 1109
1388 721
1543 641
132 52
578 1553
1964 1125
312 1045
1628 554
391 811
129 694
8 1465
80 1023
1939 38
905 256
133 1227
1331 652
764 1133
1617 873
1160 1527
1624 185
1090 1578
224 567
841 1364
1531 422
1505 1169
1785 762
490 612
183 322
1857 804
907 1884
25 375
241 86
1208 559
786 1013
833 1094
1929 1225
1604 139
1462 1899
1687 410
286 1292
1379 1837
1129 876
1887 613
1769 1756
893 326
1738 389
679 149
1919 1781
407 1427
119 1325
1272 1046
401 1131
1168 940
148 808
842 1151
1245 529
1397 919
1687 1270
815 1042
301 677
1343 452
1023 1428
677 1775
677 880
0

Output :

INFINITY
36.2215
INFINITY
0.0000
50.2494
11.1803
12.0830
8.0623
20.2485

Thank you.

[jaracz]

how to compare all pairs faster than O(n^2) it gives TLE of course