Submission #393730

---

Source Code Expand

#include<iostream>
#include<fstream>
#include<sstream>
#include<string>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<vector>
#include<list>
#include<algorithm>
#include<utility>
#include<complex>
#include<functional>
using namespace std;
#define LL long long 

struct P{
	LL x, y;
};

using namespace std;

//Compare for sorting
inline bool LessX(const P& left, const P& right){
	if (left.x == right.x)return(left.y < right.y);
	return left.x<right.x;
}
inline bool LessY(const P& left, const P& right){
	return(left.y < right.y);
}


P xx[10000000], yy[10000000],ss[10000000];
int ix, iy,is;
#define dist(_x,_y,__x,__y) (((_x)-(__x))*((_x)-(__x))+((_y)-(__y))*((_y)-(__y)))
#define distP(a,b) dist((a.x),(a.y),(b.x),(b.y))
void Closest_Pair_rec(int n,int xs, int ys, P *p1, P *p2, LL* qdist){


	P *vx = xx + xs;
	P *vy = yy + ys;

/*	cout << "vx:"; 
	for (int i = 0; i < n; i++)
		printf("(%lld,%lld)", vx[i].x, vx[i].y); cout << endl;

	for (int i = 0; i < n; i++)
		printf("(%lld,%lld)", vy[i].x, vy[i].y); cout << endl;*/
	if (n == 3){
		LL d1 = distP(vx[0], vx[1]), d2 = distP(vx[1], vx[2]), d3 = distP(vx[2], vx[0]);
		(*qdist) = d1; *p1 = vx[0], *p2 = vx[1];
		if (*qdist>d2)(*qdist) =d2,*p1 = vx[1], *p2 = vx[2];
		if (*qdist>d3)(*qdist) = d3, *p1 = vx[0] , *p2 = vx[2];
		return;
	}
	if(n==2){
		(*qdist) = distP(vx[0], vx[1]); *p1 = vx[0], *p2 = vx[1];

		return;
	}
	int half = n / 2;
	int l = iy, r = iy+half,tempiy=iy;
	P middle = vx[half];
	P rp1, rp2;
	LL  rd;
	for (int i = 0; i < n; i++){
		if (LessX(vy[i], middle))
			yy[l++] = vy[i];
		else
			yy[r++] = vy[i];
	}
	iy += n;
	Closest_Pair_rec(n / 2, xs, tempiy, p1, p2, qdist);
	Closest_Pair_rec(n-half, xs+half, tempiy+half, &rp1, &rp2, &rd);

	if (*qdist>rd)*p1 = rp1, *p2 = rp2, *qdist = rd;

	int k = 0;
	P *vs = ss + is;
	for (int i = 0; i < n; i++)
{
		rd = (vy[i].x - middle.x)*(vy[i].x - middle.x);
		if (rd < *qdist)
			vs[k++] = vy[i];
	}
	for (int i = 0; i < k - 1; i++)
		for (int j = i + 1; j < k&&vs[j].y - vs[i].y < *qdist; j++){
			rd = distP(vs[i], vs[j]);
			if (*qdist > rd){
				*qdist = rd;
				*p1 = vs[i];
				*p2 = vs[j];
			}
		}
	is += k;

}

void Closest_Pair(int n, vector<P>& list, P* p1, P* p2, LL* qdist){
	ix = n, iy = n,is=0;
	for (int i = 0; i < n; i++)
		xx[i] = yy[i] = list[i];
	sort(xx, xx+n, LessX);
	sort(yy, yy+n, LessY);
	Closest_Pair_rec(n,0,0,p1, p2, qdist);
}

int main(void){
	int N; cin >> N;
	LL a, b;
	P p1, p2;
	vector<P> A(N), B(N);
	for (int i = 0; i < N; i++){
		cin >> A[i].x >> A[i].y;
		
	}
	Closest_Pair(N, A, &p1, &p2, &a);
	for (int i = 0; i < N; i++){
		cin >> B[i].x >> B[i].y;
	}
	Closest_Pair(N, B, &p1, &p2, &b);
	//cout << b << endl;
	printf("%.6f", sqrt((double)b / (double)a));
	return(0);
}

Submission Info

Judge Result