Code: Select all
if(fabs(min-10001)<0.00001)
puts("INFINITY");
Code: Select all
if(min > 10000.0 || fabs(min-10000.0)<0.00001)
puts("INFINITY");
Moderator: Board moderators
Code: Select all
if(fabs(min-10001)<0.00001)
puts("INFINITY");
Code: Select all
if(min > 10000.0 || fabs(min-10000.0)<0.00001)
puts("INFINITY");
Code: Select all
#include <stdio.h>
#include <math.h>
int main()
{
int i,j,N;
float X[10000],Y[10000],dist,d;
do
{
scanf("%d",&N);
if(N==0) break;
dist = 10001;
for(i=0 ; i<N ; i++)
{
scanf("%f%f",&X[i],&Y[i]);
for(j=0 ; j<i ; j++)
{
d = ((X[i]-X[j])*(X[i]-X[j]))+(Y[i]-Y[j])*(Y[i]-Y[j]);
if(dist>d)
{
dist = d;
}
}
}
if(dist<=10000) printf("%.4f\n",sqrt(dist));
else printf("INFINITY\n");
} while(1);
return 0;
}
So dist basically holds the squared distance. in your if condition shouldn't you be doingamine.hamdaoui wrote:Code: Select all
.... d = ((X[i]-X[j])*(X[i]-X[j]))+(Y[i]-Y[j])*(Y[i]-Y[j]); .... if(dist<=10000) printf("%.4f\n",sqrt(dist)); else printf("INFINITY\n");
Code: Select all
dist = sqrt(dist);
if (dist <= 10000) printf("%.4f\n", dist);
else printf("INFINITY\n");
Code: Select all
if (dist <= 10000)
Code: Select all
if (dist < 10000 || fabs(dist - 10000) < 1e-7)
Code: Select all
double
Code: Select all
float
Code: Select all
#include <iostream>
#include <algorithm>
#include <string>
#include <cmath>
using namespace std;
const int sz = 10009;
const double inf = 1e20;
typedef struct node{
double x, y;
}node;
node a[sz], x[sz];
int t[sz], n;
struct cmpx{
bool operator()(const node& lhs, const node& rhs)
{
return lhs.x < rhs.x;
}
};
struct cmpy{
bool operator()(const node& lhs, const node& rhs)
{
return lhs.y < rhs.y;
}
};
double closest_pair(int l, int r)
{
int j, k, p, m;
double dx, dy;
double ans, delta;
if(r - l <= 2){
for(j = l, ans = inf; j <= r - 1; j++){
for(k = j + 1; k <= r; k++){
dx = a[j].x - a[k].x;
dy = a[j].y - a[k].y;
if(dx * dx + dy * dy < ans){
ans = dx * dx + dy * dy;
}
}
}
return ans;
}
else{
m = l + (r - l)/2;
ans = min(closest_pair(l, m), closest_pair(m + 1, r));
delta = sqrt(ans);
for(j = l, k = 0; j <= r; j++){
if( (x[m].x - a[j].x) <= delta){
t[k++] = j;
}
}
for(j = 0; j < k; j++){
for(p = j + 1; p < k && (a[t[p]].y - a[t[j]].y) <= delta; p++){
dx = a[t[j]].x - a[t[p]].x;
dy = a[t[j]].y - a[t[p]].y;
if(dx * dx + dy * dy < ans){
ans = dx * dx + dy * dy;
}
}
}
return ans;
}
}
int main()
{
int j;
double ans;
while(scanf("%d", &n) && n){
for(j = 0; j < n; j++){
scanf("%lf%lf", &a[j].x, &a[j].y);
x[j] = a[j];
}
if(n == 1){
printf("INFINITY\n");
}
else{
sort(a, a + n, cmpy());
sort(x, x + n, cmpx());
ans = closest_pair(0, n - 1);
ans = sqrt(ans);
if(ans - 10000 >= 1e-10){
printf("INFINITY\n");
}
else{
printf("%.4f\n", ans);
}
}
}
return 0;
}
Code: Select all
program u10245;
var
ans:double;
n,i:longint;
a:array[0..10000,1..2]of double;
function dis(o1,o2:longint):double;
var
t:double;
begin
t:=sqrt(sqr(a[o1,1]-a[o2,1])+sqr(a[o1,2]-a[o2,2]));
exit(t);
end;
function min(o1,o2:double):double;
begin
if o1<o2
then exit(o1)
else exit(o2);
end;
procedure qs(l,r:longint;ip:integer);
var
m:double;
i,j:longint;
t:array[1..2]of double;
begin
i:=l;j:=r;m:=a[(i+j)shr 1,ip];
repeat
while a[i,ip]<m do inc(i);
while m<a[j,ip] do dec(j);
if i<=j
then begin
t:=a[i];
a[i]:=a[j];
a[j]:=t;
inc(i);
dec(j);
end;
until i>j;
if i<r then qs(i,r,ip);
if l<j then qs(l,j,ip);
end;
function ef(l,r:longint):double;
var
mid,m,i,j,k,o,x,ll,rr:longint;
e:double;
begin
if l=r
then exit(10001);
mid:=(l+r)shr 1;
e:=min(ef(mid+1,r),ef(l,mid));
i:=mid;j:=mid;
qs(l,r,1);
while (a[i,1]>a[mid,1]-e)and(i>l) do dec(i);
while (a[j,1]<a[mid,1]+e)and(j<r) do inc(j);
qs(i,mid,2);
qs(mid+1,j,2);
if mid<j
then
for k:=i to mid do
begin
ll:=mid+1;rr:=j;x:=ll;
while ll<rr do
if a[rr,2]<a[k,2]
then begin
x:=rr;
break;
end
else if a[ll,2]>=a[k,2]
then begin
x:=ll;
break;
end
else begin
m:=(ll+rr)shr 1;
if a[m,2]<=a[k,2]
then rr:=m
else ll:=m;
x:=rr;
end;
for o:=x downto x-3 do
if o<mid+1
then break
else e:=min(e,dis(k,o));
for o:=x+1 to x+4 do
if o>j
then break
else e:=min(e,dis(k,o));
end;
exit(e);
end;
procedure int(n:longint);
var
i:longint;
begin
for i:=1 to n do
readln(a[i,1],a[i,2]);
end;
begin
readln(n);
while n<>0 do
begin
int(n);
qs(1,n,1);
ans:=ef(1,n);
if ans>=9999.99995
then writeln('INFINITY')
else writeln(ans:0:4);
readln(n);
end;
end.
Code: Select all
#define INFINITY 10000
#include <iostream>
using std::cin;
using std::cout;
using std::endl;
using std::fixed;
#include <iomanip>
using std::setprecision;
#include <algorithm>
using std::sort;
#include <cmath>
using std::sqrt;
using std::fabs;
using std::min;
struct Point
{
int index;
double x, y;
};
Point xP [ 10000 ];
Point yP [ 10000 ];
double xMess [ 10000 ];
double yMess [ 10000 ];
bool isLeft [ 10000 ];
Point yStrip [ 10000 ];
int n;
void process();
bool cmpFnX( Point p1, Point p2 );
bool cmpFnY( Point p1, Point p2 );
double cpp( int stInd, int endInd, int yInds [] );
double distance( Point p1, Point p2 );
int main()
{
cin >> n;
while ( n != 0 )
{
double tX, tY;
for ( int i = 0; i < n; i++ )
{
cin >> tX >> tY;
xP[ i ].index = yP[ i ].index = i;
xMess[ i ] = xP[ i ].x = yP[ i ].x = tX;
yMess[ i ] = xP[ i ].y = yP[ i ].y = tY;
}
process();
cin >> n;
}
return 0;
}
void process()
{
sort( &xP[ 0 ], &xP[ n ], cmpFnX );
sort( &yP[ 0 ], &yP[ n ], cmpFnY );
int firstYInds [ 10000 ];
for ( int i = 0; i < n; i++ )
{
firstYInds[ i ] = yP[ i ].index;
}
double result = cpp( 0, n - 1, firstYInds );
if ( result >= INFINITY )
{
cout << "INFINTIY" << endl;
}
else
{
cout << fixed << setprecision( 4 ) << result << endl;
}
}
double cpp( int stInd, int endInd, int yInds [] ) // stInd and endInd are on xP
{
int pNo = endInd - stInd + 1;
int yIndsL [ 5000 ];
int yIndsR [ 5000 ];
if ( pNo == 1 )
{
return INFINITY;
}
else if ( pNo == 2 )
{
return distance( xP[ 0 ], xP[ 1 ] );
}
else if ( pNo >= 3 ) // number of points is more than or equal to 3
{
int mid = ( stInd + endInd ) / 2;
for ( int i = stInd; i <= mid; i++ )
{
isLeft[ xP[ i ].index ] = true;
}
for ( int i = mid + 1; i <= endInd; i++ )
{
isLeft[ xP[ i ].index ] = false;
}
int k1 = 0;
int k2 = 0;
for ( int i = 0; i < pNo; i++ )
{
if ( isLeft[ yInds[ i ] ] == true )
{
yIndsL[ k1++ ] = yInds[ i ];
}
else
{
yIndsR[ k2++ ] = yInds[ i ];
}
}
double distL, distR;
if ( stInd <= mid )
{
distL = cpp( stInd, mid, yIndsL );
}
else
{
distL = INFINITY;
}
if ( mid + 1 <= endInd )
{
distR = cpp( mid + 1, endInd, yIndsR );
}
else
{
distR = INFINITY;
}
double lrDist = min( distL, distR );
Point midPoint = xP[ mid ];
// Construct yStrip array, in increasing y order
int strCnt = 0;
for ( int i = 0; i < pNo; i++ )
{
if ( fabs( xMess[ yInds[ i ] ] - midPoint.x ) < lrDist )
{
yStrip[ strCnt ].x = xMess[ yInds[ i ] ];
yStrip[ strCnt ].y = yMess[ yInds[ i ] ];
// no need to initialize yStrip[strCnt].index
strCnt++;
}
}
// yStrip constructed
double minDist = lrDist;
for ( int i = 0; i < strCnt - 1; i++ )
{
double tDist;
for ( int j = i + 1; j < strCnt && yStrip[ j ].y - yStrip[ i ].y < lrDist; j++ ) // why lrDist, why not minDist?!
{
tDist = distance( yStrip[ j ], yStrip[ i ] );
minDist = min( tDist, minDist );
}
}
return minDist;
}
}
double distance( Point p1, Point p2 )
{
return sqrt( ( p1.x - p2.x ) * ( p1.x - p2.x ) +
( p1.y - p2.y ) * ( p1.y - p2.y ) + 0.0 );
}
bool cmpFnX( Point p1, Point p2 )
{
return p1.x < p2.x;
}
bool cmpFnY( Point p1, Point p2 )
{
return p1.y < p2.y;
}
Code: Select all
#define INFIN 10000
#include <iostream>
using std::cin;
using std::cout;
using std::endl;
using std::fixed;
#include <iomanip>
using std::setprecision;
#include <algorithm>
using std::sort;
#include <cmath>
using std::sqrt;
using std::fabs;
using std::min;
struct Point
{
int index;
double x, y;
};
Point xP [ 10000 ];
Point yP [ 10000 ];
double xMess [ 10000 ];
double yMess [ 10000 ];
bool isLeft [ 10000 ];
Point yStrip [ 10000 ];
int n;
void process();
bool cmpFnX( Point p1, Point p2 );
bool cmpFnY( Point p1, Point p2 );
double cpp( int stInd, int endInd, int yInds [] );
double distance( Point p1, Point p2 );
int main()
{
cin >> n;
while ( n != 0 )
{
double tX, tY;
for ( int i = 0; i < n; i++ )
{
cin >> tX >> tY;
xP[ i ].index = yP[ i ].index = i;
xMess[ i ] = xP[ i ].x = yP[ i ].x = tX;
yMess[ i ] = xP[ i ].y = yP[ i ].y = tY;
}
process();
cin >> n;
}
return 0;
}
void process()
{
sort( &xP[ 0 ], &xP[ n ], cmpFnX );
sort( &yP[ 0 ], &yP[ n ], cmpFnY );
int firstYInds [ 10000 ];
for ( int i = 0; i < n; i++ )
{
firstYInds[ i ] = yP[ i ].index;
}
double result = cpp( 0, n - 1, firstYInds );
if ( result >= INFIN )
{
cout << "INFINTIY" << endl;
}
else
{
cout << fixed << setprecision( 4 ) << result << endl;
}
}
double cpp( int stInd, int endInd, int yInds [] ) // stInd and endInd are on xP
{
int pNo = endInd - stInd + 1;
int yIndsL [ 5000 ];
int yIndsR [ 5000 ];
if ( pNo == 1 )
{
return INFIN;
}
else if ( pNo == 2 )
{
return distance( xP[ stInd ], xP[ endInd ] );
}
else if ( pNo >= 3 ) // number of points is more than or equal to 3
{
int mid = ( stInd + endInd ) / 2;
for ( int i = stInd; i <= mid; i++ )
{
isLeft[ xP[ i ].index ] = true;
}
for ( int i = mid + 1; i <= endInd; i++ )
{
isLeft[ xP[ i ].index ] = false;
}
int k1 = 0;
int k2 = 0;
for ( int i = 0; i < pNo; i++ )
{
if ( isLeft[ yInds[ i ] ] == true )
{
yIndsL[ k1++ ] = yInds[ i ];
}
else
{
yIndsR[ k2++ ] = yInds[ i ];
}
}
double distL, distR;
if ( stInd <= mid )
{
distL = cpp( stInd, mid, yIndsL );
}
else
{
distL = INFIN;
}
if ( mid + 1 <= endInd )
{
distR = cpp( mid + 1, endInd, yIndsR );
}
else
{
distR = INFIN;
}//cout << distL << " " << distR << endl;
double lrDist = min( distL, distR );
Point midPoint = xP[ mid ];
// Construct yStrip array, in increasing y order
int strCnt = 0;
for ( int i = 0; i < pNo; i++ )
{
if ( fabs( xMess[ yInds[ i ] ] - midPoint.x ) < lrDist )
{
yStrip[ strCnt ].x = xMess[ yInds[ i ] ];
yStrip[ strCnt ].y = yMess[ yInds[ i ] ];
// no need to initialize yStrip[strCnt].index
strCnt++;
}
}
// yStrip constructed
double minDist = lrDist;
for ( int i = 0; i < strCnt - 1; i++ )
{
double tDist;
for ( int j = i + 1; j < strCnt && yStrip[ j ].y - yStrip[ i ].y < lrDist; j++ ) // why lrDist, why not minDist?!
{
tDist = distance( yStrip[ j ], yStrip[ i ] );
minDist = min( tDist, minDist );
}
}
return minDist;
}
}
double distance( Point p1, Point p2 )
{
return sqrt( ( p1.x - p2.x ) * ( p1.x - p2.x ) +
( p1.y - p2.y ) * ( p1.y - p2.y ) + 0.0 );
}
bool cmpFnX( Point p1, Point p2 )
{
return p1.x < p2.x;
}
bool cmpFnY( Point p1, Point p2 )
{
return p1.y < p2.y;
}
Code: Select all
2
0 0
7071.0678118654752440084436210485 7071.0678118654752440084436210485
0