10245 - The Closest Pair Problem

All about problems in Volume 102. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
yatsen
Learning poster
Posts: 68
Joined: Fri Nov 23, 2001 2:00 am
Location: taiwan

Post by yatsen » Wed Mar 20, 2002 9:43 am

I got Time Limit Exceeded for this problem.
I use 2 for loop to caculate all pair distance.
Can anyone tell me what's wrong?

junjieliang
Experienced poster
Posts: 169
Joined: Wed Oct 31, 2001 2:00 am
Location: Singapore

Post by junjieliang » Wed Mar 20, 2002 11:49 am

Look at the limit: N <= 10000. Given a O(n^2) method you'll never get it to run in time.

Btw, the quote at the bottom fits exactly into this situation...

yatsen
Learning poster
Posts: 68
Joined: Fri Nov 23, 2001 2:00 am
Location: taiwan

Post by yatsen » Thu Mar 21, 2002 2:17 am


Stefan Pochmann
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:

Post by Stefan Pochmann » Thu Mar 21, 2002 3:15 am

Go for O(n log n). Get yourself the book of Cormen, Leiserson, Rivest (and Stein in the 2nd edition), if you want the algorithm explained. It's not the easiest algorithm I've ever seen...

Stefan Pochmann
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:

Post by Stefan Pochmann » Thu Mar 21, 2002 3:19 am

Btw, in a local contest we once had a similar problem and I wrote a fake because we didn't have enough time. I splitted the world into a grid and only checked pairs in the same or in adjacent cells. Didn't work here, unfortunately. But back then, it did. There are two extremes. If you make the cells too large, you'll end up with n^2 and runtime-limit exceeded again. If you make them too small, you'll get wrong answer. But somewhere in between may lie an "accepted" :wink:

Ivan Golubev
Experienced poster
Posts: 167
Joined: Fri Oct 19, 2001 2:00 am
Location: Saint Petersburg, Russia

Post by Ivan Golubev » Thu Mar 21, 2002 12:52 pm

Actually O(n^2) isn't so large as you think. So this problem can be solved only with stupid brute-force, as I did. It rans for 19 seconds but it's enough to fit into time limit. Of course, while checking distance don't use sqrt. It must be used only once, before outputting result.

Stefan Pochmann
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:

Post by Stefan Pochmann » Thu Mar 21, 2002 12:55 pm

Yeah, right. But can you live with the shame of having such a naive solution? :wink:

shahriar_manzoor
System administrator & Problemsetter
Posts: 399
Joined: Sat Jan 12, 2002 2:00 am

Post by shahriar_manzoor » Thu Mar 21, 2002 1:13 pm

Actually it's time limit was 8 seconds in the contest, and its judge data was prepared accordingly. But I am afraid that the OJ decides to keep time limit for all problems as 30 seconds in 24-hour judge. So I will have to come up with new idea! more judge datas :smile:

<font size=-1>[ This Message was edited by: shahriar_manzoor on 2002-03-21 12:14 ]</font>

Caesum
Experienced poster
Posts: 225
Joined: Fri May 03, 2002 12:14 am
Location: UK
Contact:

10245 input

Post by Caesum » Fri May 03, 2002 12:17 am

After much messing with this problem I seem to be timing out on trying to parse the input file. Am I right in saying that the input is full of non-numeric characters as my usual scanf("%u",&n) just seems to hang. In the end I have written something based on getc(stdin) hunting for numeric digits, but now some of the arrays seem to be bigger then 10000 as stated in the question. Is there something funny going on here or am I missing something ?

Ivan Golubev
Experienced poster
Posts: 167
Joined: Fri Oct 19, 2001 2:00 am
Location: Saint Petersburg, Russia

Post by Ivan Golubev » Fri May 03, 2002 12:32 am

Hmm, there nothing about 'only integers in input' in the problem statement. Why not to use scanf("%lf", &x) ?

M.Z
New poster
Posts: 3
Joined: Sat Jul 20, 2002 4:48 am

10245

Post by M.Z » Sun Aug 04, 2002 7:41 pm

my method is O(n*log(n)) But Wrong answer.
any one can help me!
thank you!

[cpp]
#include<iostream.h>
#include<stdio.h>
#include<math.h>

#include<fstream.h>
ifstream in("es_10245.in");
//#define in cin

const double eps=1e-14;
struct point{
double x,y;
} p[10000];
int N;


void swap(int i,int j)
{
double temp;
temp=p.x;
p.x=p[j].x;
p[j].x=temp;

temp=p.y;
p.y=p[j].y;
p[j].y=temp;
}

int partition(int low,int high)
{
int i;
int last_small;
double pivot;

swap(low,(low+high)/2);
pivot=p[low].x;
last_small=low;
for(i=low+1;i<=high;i++){
if(p.x-pivot<eps){
last_small++;
swap(last_small,i);
}
}
swap(low,last_small);
return last_small;
}

void qsort(int i,int j)
{
int pos;
if(i<j){
pos=partition(i,j);
qsort(i,pos-1);
qsort(pos+1,j);
}
}

void merge_sort(int low,int mid,int high)
{
int p1,p2,pointer;
int i;
point temp[10000];

p1=low;
p2=mid+1;
pointer=low;
while(p1<=mid&&p2<=high){
if(p[p1].y-p[p2].y<eps){
temp[pointer].x=p[p1].x;
temp[pointer++].y=p[p1++].y;
}else{
temp[pointer].x=p[p2].x;
temp[pointer++].y=p[p2++].y;
}
}
if(p1<=mid){
temp[pointer].x=p[p1].x;
temp[pointer++].y=p[p1++].y;
}
for(i=low;i<pointer;i++){
p.x=temp.x;
p.y=temp.y;
}
}

void init()
{
int i;
for(i=0;i<N;i++)
in>>p.x>>p[i].y;
qsort(0,N-1);
}

double dist(int i,int j)
{
return sqrt((p[i].x-p[j].x)*(p[i].x-p[j].x)+(p[i].y-p[j].y)*(p[i].y-p[j].y));
}

double clost_pair(int low,int high)
{
double t,ans1,ans2,ans;
double l;
int index,mid;
point temp[10000];
int i,j,k,s;

if(high-low<3){
for(i=low;i<high;i++)
for(j=i+1;j<=high;j++)
if(p[i].y-p[j].y>eps) swap(i,j);
ans=dist(low,low+1);
for(i=low;i<high;i++)
for(j=i+1;j<=high;j++){
t=dist(i,j);
if(ans-t>eps) ans=t;
}
return ans;
}

mid=(low+high)/2;
l=p[mid].x;
ans1=clost_pair(low,mid);
ans2=clost_pair(mid+1,high);
if(ans1-ans2<eps) ans=ans1;else ans=ans2;
merge_sort(low,mid,high);

index=0;
for(k=low;k<=high;k++){
if((p[k].x-(l-ans)>eps)&&((l+ans)-p[k].x>eps)){
temp[index].x=p[k].x;
temp[index++].y=p[k].y;
}
}
for(k=0;k<index-1;k++)
for(s=k+1;s<index&&s<k+7;s++){
t=sqrt((temp[k].x-temp[s].x)*(temp[k].x-temp[s].x)+(temp[k].y-temp[s].y)*(temp[k].y-temp[s].y));
if(ans-t>eps) ans=t;
}
return ans;
}

void main()
{
double dist;
while(1){
in>>N;
if(!N) break;
init();
if(N==1) printf("INFINITY\n");
else{
dist=clost_pair(0,N-1);
if(10000.0-dist>eps) printf("%.4lf\n",dist);
else printf("INFINITY\n");
}
}
}[/cpp]

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

10245 - The Closest Pair Problem

Post by Larry » Fri Nov 01, 2002 2:07 am

Is there trick input on 10245? The acceptance rate seems to be low, and I keep getting WA =(

rjhadley
Learning poster
Posts: 73
Joined: Mon Oct 14, 2002 7:15 am
Location: United States

Post by rjhadley » Thu Jan 02, 2003 5:35 am

It took me two tries to get Accepted. The only changes between the two versions were:

1) If there is only one point in the data set then output INFINITY instead of garbage. (This is only trick input I can think of).

2) Only use sqrt() when necessary instead of for every distance calculation. (This will speed it up slightly and perhaps avoid some weird floating point rounding errors).

3) Use the reserve() method in my C++ vectors. (For a very minor speed improvement).

So take your pick between #1, #2, and/or a lot of buggy/slow programs being submitted as the cause of the low acceptance rate.

anak_papua
New poster
Posts: 7
Joined: Wed Mar 19, 2003 3:16 pm

10245 - Output Limit Exceeded

Post by anak_papua » Mon Mar 31, 2003 6:08 am

why OJ gave my code Output Limit Exceeded? :evil: :evil: :evil:
i didnt see anything that could give me that.
[c]
/*@JUDGE_ID: XXXXX 10245 C*/
#include <stdio.h>
#include <math.h>

#define MAX 10002

typedef struct {
unsigned long x, y;
} tdata;

tdata data[MAX];

int main () {
int jum, i, j;
unsigned long x, y, res, min;
char ch;

while (1) {
scanf ("%d", &jum);
if (jum == 0)
break;

for (i = 0; i < jum; i++)
scanf ("%lu %lu", &data.x, &data.y);
min = 100000000;
if (jum > 1) {
for (i = 0; i < jum-1; i++)
for (j = i + 1; j < jum; j++) {
x = (data.x - data[j].x) * (data.x - data[j].x);
y = (data.y - data[j].y) * (data.y - data[j].y);
res = x + y;
if (res < min)
min = res;
}
}
if (min == 100000000)
printf ("INFINITY\n");
else
printf ("%.4f\n", sqrt (min));
}
return 0;
}
[/c]

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Mon Jun 09, 2003 8:09 am

Nice hint rhadley :):)
I miss in description that for one point I should print INFINITY :)
But now I'm Accepted this problem :) and with nice time (less then 0.7 sec)

Thanks again for hint :)
DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

Post Reply

Return to “Volume 102 (10200-10299)”