10245  The Closest Pair Problem
Moderator: Board moderators

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

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

 A great helper
 Posts: 284
 Joined: Thu Feb 28, 2002 2:00 am
 Location: Germany
 Contact:
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 runtimelimit exceeded again. If you make them too small, you'll get wrong answer. But somewhere in between may lie an "accepted"

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

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

 System administrator & Problemsetter
 Posts: 399
 Joined: Sat Jan 12, 2002 2:00 am
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 24hour judge. So I will have to come up with new idea! more judge datas
<font size=1>[ This Message was edited by: shahriar_manzoor on 20020321 12:14 ]</font>
<font size=1>[ This Message was edited by: shahriar_manzoor on 20020321 12:14 ]</font>
10245 input
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 nonnumeric 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 ?

 Experienced poster
 Posts: 167
 Joined: Fri Oct 19, 2001 2:00 am
 Location: Saint Petersburg, Russia
10245
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=1e14;
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.xpivot<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,pos1);
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].yp[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,N1);
}
double dist(int i,int j)
{
return sqrt((p[i].xp[j].x)*(p[i].xp[j].x)+(p[i].yp[j].y)*(p[i].yp[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(highlow<3){
for(i=low;i<high;i++)
for(j=i+1;j<=high;j++)
if(p[i].yp[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(anst>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(ans1ans2<eps) ans=ans1;else ans=ans2;
merge_sort(low,mid,high);
index=0;
for(k=low;k<=high;k++){
if((p[k].x(lans)>eps)&&((l+ans)p[k].x>eps)){
temp[index].x=p[k].x;
temp[index++].y=p[k].y;
}
}
for(k=0;k<index1;k++)
for(s=k+1;s<index&&s<k+7;s++){
t=sqrt((temp[k].xtemp[s].x)*(temp[k].xtemp[s].x)+(temp[k].ytemp[s].y)*(temp[k].ytemp[s].y));
if(anst>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,N1);
if(10000.0dist>eps) printf("%.4lf\n",dist);
else printf("INFINITY\n");
}
}
}[/cpp]
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=1e14;
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.xpivot<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,pos1);
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].yp[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,N1);
}
double dist(int i,int j)
{
return sqrt((p[i].xp[j].x)*(p[i].xp[j].x)+(p[i].yp[j].y)*(p[i].yp[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(highlow<3){
for(i=low;i<high;i++)
for(j=i+1;j<=high;j++)
if(p[i].yp[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(anst>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(ans1ans2<eps) ans=ans1;else ans=ans2;
merge_sort(low,mid,high);
index=0;
for(k=low;k<=high;k++){
if((p[k].x(lans)>eps)&&((l+ans)p[k].x>eps)){
temp[index].x=p[k].x;
temp[index++].y=p[k].y;
}
}
for(k=0;k<index1;k++)
for(s=k+1;s<index&&s<k+7;s++){
t=sqrt((temp[k].xtemp[s].x)*(temp[k].xtemp[s].x)+(temp[k].ytemp[s].y)*(temp[k].ytemp[s].y));
if(anst>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,N1);
if(10000.0dist>eps) printf("%.4lf\n",dist);
else printf("INFINITY\n");
}
}
}[/cpp]

 Guru
 Posts: 647
 Joined: Wed Jun 26, 2002 10:12 pm
 Location: Hong Kong and New York City
 Contact:
10245  The Closest Pair Problem
Is there trick input on 10245? The acceptance rate seems to be low, and I keep getting WA =(
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.
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.

 New poster
 Posts: 7
 Joined: Wed Mar 19, 2003 3:16 pm
10245  Output Limit Exceeded
why OJ gave my code Output Limit Exceeded?
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 < jum1; 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]
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 < jum1; 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]

 Guru
 Posts: 834
 Joined: Wed May 29, 2002 4:11 pm
 Location: Wroclaw, Poland
 Contact:
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
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)
Born from ashes  restarting counter of problems (800+ solved problems)