알고리즘 아이디어..

#include <iostream>
#include <algorithm>
#include <iomanip>
#include <cmath>
 
 
 
using namespace std;
 
const int MAX = 10001;
 
struct point{
	int x,y;
};
 
bool xCompare(struct point, struct point);
bool yCompare(struct point, struct point);
int dis(struct point, struct point);
 
int absd(int);
int trace(int,int,int,int);
 
point p[MAX], q[MAX], tmp[MAX];
 
int main(){
 
    int left;
    int right;
 
    scanf("%d\n", &left);
    memset(p,0,sizeof(p));
    memset(q,0,sizeof(q));
    memset(tmp,0,sizeof(tmp));
 
 
    for(int i=0; i<left; i++){
        cin >> p[i].x >> p[i].y;
    }
 
    scanf("%d\n", &right);
 
    for(int j=0; j<right; j++){
        cin >> q[j].x >> q[j].y;
    }
 
    sort(p, p+left, xCompare);
    sort(q, q+right, xCompare);
 
    int min = trace(0,0, left-1, right-1);
 
    printf("%d\n", min);
 
 
    /**
	while(true){
		cin >> n;
 
		if(n == 0)	break;
 
		memset(p,0,sizeof(p));
		memset(tmp,0,sizeof(tmp));
 
		for(int i= 0;i<n;i++)
			cin >> p[i].x >> p[i].y;
 
		sort(p,p+n,xCompare);
 
		int min = trace(0,n-1);
 
		if(min < 10000 && n > 1){
			cout << fixed;
			cout << setprecision(4) << min << endl;
		}
		else
			cout << "INFINITY" << endl;
	}
     **/
 
	return 0;
}
 
int trace(int low1, int low2, int high1, int high2){
 
	if(high1 - low1 < 3){
		int value = dis(p[low1],q[low2+1]);
		int nextValue;
 
		if(high1 - low1 == 2){	
			nextValue = dis(p[low1],q[low2+2]);
 
			if(value > nextValue)
				value = nextValue;
 
			nextValue = dis(p[low1+1],q[low2+2]);
 
			if(value > nextValue)
				value = nextValue;
		}
		return value;
	}
	else{
 
		/* DIVIDE & QONQUER */
 
		int mid1 = (low1 + high1) >> 1;
        int mid2 = (low2 + high2) >> 1;
		int cnt = 0;
 
		int leftValue = trace(low1,low2,mid1,mid2);		// left trace
		int rightValue = trace(mid1+1,mid2+1,high1,high2);	// right trace
 
		// min value find
		int value = leftValue < rightValue ? leftValue : rightValue;
 
		/* Middle Condition Check : Y Line */
 
		// saving left
		for(int i = low1;i<=mid1;i++){
			if(abs(p[i].x - q[mid2].x) <= value)
				tmp[cnt++] = p[i];
		}
 
		// saving right
		for(int i = mid1+1;i<=high1;i++){
			if(absd(p[i].x - q[mid2+1].x) <= value)
				tmp[cnt++] = p[i];
		}
 
		sort(tmp,tmp+cnt,yCompare);
 
		for(int i = 0;i<cnt;i++){
			int count = 0;
 
			for(int j = i-3;count < 6 && j < cnt;j++){
				if(j >= 0 && i != j){
					int distance = dis(tmp[i],tmp[j]);
 
					if(value > distance)
						value = distance;
 
					count++;
				}
			}
		}
		return value;
	}
}
 
int absd(int x){
	if( x < 0)
		return -x;
	return x;
}
 
int dis(struct point a, struct point b){
	return (abs(a.x-b.x) + abs(a.y-b.y));
}
 
bool xCompare(struct point a, struct point b){
	return a.x < b.x;
}
 
bool yCompare(struct point a, struct point b){
	return a.y < b.y;
}