[UVA][最鄰近點對] 11378 - Bey Battle
Problem B
Bey Battle
Time Limit: 4 Second
Dark Blader has returned with new tactics. They are now able to create an energy field around its blade and if any blade enters inside any of these energy fields the energy level of the Bit-beast drastically decreases. So Tyson had to avoid these energy fields and finally he has won!
I was lucky enough to be around Kenny who was analyzing the game with his PC and helping Tyson to avoid the energy field. I saw that the energy field was Square in shape and the blade was at its centre. At that instant a problem came to my mind and let me see how efficiently you can solve that problem.
There will be N points in a 2D plane. Find out the maximum size such that if you draw such size squares around each point (that point will be at the center of the square) no two squares will intersect each other (can touch but not intersect). To make the problem simple the sides of the squares will be parallel to X and Y axis.
Input:
Input contains several test cases. Each case starts with N which will be at most 10,000 except one case which will be 100,000. Then there are N lines- pairs of integers denoting the coordinate of each point. The absolute value of the integers can be at most 1,000,000. X or Y coordinate of any two points will be unequal.
Output:
Output a single line for each test case- maximum side length of square.
|
SAMPLE INPUT |
OUTPUT FOR SAMPLE INPUT |
|
2 0 0 2 2 |
2 |
Problemsetter: Md. Mahbubul Hasan
題目描述：
平面上有 N 個點，將每個點都做為中心的正方形，其邊長都要一樣。
問這些正方形不牴觸(不相交)的最大邊長為何？
解法：
說是最大邊長，事實上也是拋棄 "歐幾里德距離"，
計算任兩點 max(abs(pi.x - pj.x), abs(pi.y - pj.y)) 最小化為多少。
用最鄰近點對的 D&C 去解決。
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
struct Pt {
int x, y;
bool operator<(const Pt &a) const {
if(x != a.x)
return x < a.x;
return y < a.y;
}
};
Pt D[100005];
void closestPair(int l, int r, int &ret) {
if(l >= r) return;
int m = (l+r)/2;
closestPair(l, m, ret);
closestPair(m+1, r, ret);
static int i, j;
for(i = m; i >= l; i--) {
if(D[m].x-D[i].x >= ret)
break;
for(j = m+1; j <= r; j++) {
if(D[j].x-D[i].x >= ret)
break;
ret = min(ret, max(D[j].x-D[i].x, abs(D[j].y-D[i].y)));
}
}
}
int main() {
int n, i;
while(scanf("%d", &n) == 1) {
for(i = 0; i < n; i++)
scanf("%d %d", &D[i].x, &D[i].y);
sort(D, D+n);
int ret = 0xfffffff;
closestPair(0, n-1, ret);
printf("%d\n", ret);
}
return 0;
}
Thank you..