ZOJ2107
HDU1007
POJ3714
#include <iostream>
#include<cstdio>
#include<string.h>
#include<algorithm>
#include <cmath>
#include<iomanip>
#include <assert.h>
using namespace std;
int n;
struct node{
double x;
double y;
};
node s[100001];
node tempC[100001];//用于临时比较的辅助数组
node ta[100001];
double Distance(node a, node b) {
return sqrt((a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y));
}
//按x从小到大排序
bool cmp1(node a, node b) {
return a.x < b.x;
}
//按y从小到大排序
bool cmp2(node a, node b) {
return a.y < b.y;
}
int merge(int left, int right,int middle,int axis,double delta){
int i, j, index1, index2;
int cm=0;
for (j = left; j <= right; ++j)
ta[j] = s[j];
index1 = left;
index2 = middle + 1;
i = left;
while (index1 <= middle && index2 <= right){
if (ta[index1].y <= ta[index2].y){
s[i] = ta[index1];
//将距离AXIS 在delta以内的点放到辅助空间，同时保持y升序
if (double(abs(s[i].x - axis)) <= delta) {
tempC[cm] = s[i];
++cm;
}
++i;
++index1;
}else{
s[i] = ta[index2];
if (double(abs(s[i].x - axis)) <= delta){
tempC[cm] = s[i];
++cm;
}
++i;
++index2;
}
}
while (index1 <= middle){
s[i] = ta[index1];
if (double(abs(s[i].x - axis)) <= delta){
tempC[cm] = s[i];
++cm;
}
++i;
++index1;
}
while (index2 <= right){
s[i] = ta[index2];
if (double(abs(s[i].x - axis)) <= delta){
tempC[cm] = s[i];
++cm;
}
++i;
++index2;
}
return cm - 1;
}
//采用按点数分治，s,e分别为处理坐标的起止
double solveClosest(int start, int end) {
double tempans = Distance(s[start],s[end]);
double d1, d2, d3=0;
if (end - start == 1) {//两个点的情况
sort(s + start, s + end+1, cmp2); //保持y序列的有序
return Distance(s[end], s[start]);
}
if (end - start == 2) {//三个点的情况
d1 = Distance(s[start], s[start + 1]);
d2 = Distance(s[start + 1], s[end]);
d3 = Distance(s[end], s[start]);
sort(s + start, s + end+1, cmp2); //保持y序列的有序
if ((d1<= d2) && (d1<= d3)) {
return d1;
}else if (d2<= d3){
return d2;
}else return d3;
}
int mid = (start + end) / 2;
d1 =solveClosest(start, mid);
d2 =solveClosest(mid + 1, end);
if(d1<=d2) tempans = d1; //开始考察两区域中间的情况 此时左右区间已经内部按y升序
else tempans = d2;
for (int i = 0; i < end - start + 1; ++i){
tempC[i].x = 0;
tempC[i].y = 0;
}
int cnt = 0;
cnt =merge(start, end, mid, s[mid].x , tempans);//进行归并排序中的合并，并且同时挑出在轴值附近需要比较的所有点（且按照y升序排列）
//比较每一个tempC[i]所可能产生的最小距离
for (int i = 0; i < cnt; ++i) {
int ui = i-1;
int di = i + 1;
while (ui >= 0 && double(abs(tempC[ui].y - tempC[i].y)) <= tempans){
if (Distance(tempC[ui], tempC[i]) < tempans)
tempans = Distance(tempC[ui], tempC[i]);
--ui;
}
while (di <= cnt && double(abs(tempC[di].y - tempC[i].y)) <= tempans){
if (Distance(tempC[di], tempC[i]) < tempans)
tempans = Distance(tempC[di], tempC[i]);
++di;
}
}
return tempans;
}
int main(){
while(~scanf("%d", &n) && n) {
for(int i = 0; i < n; ++i) {
scanf("%lf%lf", &s[i].x, &s[i].y);
}
sort(s, s + n, cmp1); //先按x从小到大排序
double ans = solveClosest(0, n - 1);
printf("%.2f
", ans/2);
}
return 0;
}
#include <iostream>
#include <vector>
#include<string.h>
#include<algorithm>
#include <cmath>
#include<iomanip>
#include <assert.h>
#include <cstdio>
using namespace std;
struct point {
double x;
double y;
point(double x, double y) :x(x), y(y) {}
point() { return; }
};
bool cmp_x(const point & A, const point & B) {
return A.x < B.x;
}
bool cmp_y(const point & A, const point & B) {
return A.y < B.y;
}
double distance(const point & A, const point & B){
return sqrt(pow(A.x - B.x, 2) + pow(A.y - B.y, 2));
}
/*
* function: 合并，同第三区域最近点距离比较
* param: points 点的集合
* dis 左右两边集合的最近点距离
* mid x坐标排序后，点集合中中间点的索引值
*/
double merge(vector<point> & points, double dis, int mid){
vector<point> left, right;
// 搜集左右两边符合条件的点
for (int i = 0; i < (int)points.size(); ++i) {
if (points[i].x - points[mid].x <= 0 && points[i].x - points[mid].x > -dis)
left.push_back(points[i]);
else if (points[i].x - points[mid].x > 0 && points[i].x - points[mid].x < dis)
right.push_back(points[i]);
}
sort(right.begin(), right.end(), cmp_y);
// 遍历左边的点集合，与右边符合条件的计算距离
for (int i = 0, index; i < left.size(); ++i) {
for (index = 0; index < right.size() && left[i].y > right[index].y; ++index);
// 遍历右边坐标上界的6个点
for (int j = 0; j < 7 && index + j < right.size(); ++j) {
if (distance(left[i], right[j + index]) < dis)
dis = distance(left[i], right[j + index]);
}
if(index == right.size()) index --;
// 遍历右边坐标上界的6个点
for (int j = 0; j < 7; ++j) {
if(index-j < 0) break;
if (distance(left[i], right[index-j]) < dis)
dis = distance(left[i], right[index-j]);
}
}
return dis;
}
double closest(vector<point> & points){
if ((int)points.size() == 2) return distance(points[0], points[1]); // 两个点
if ((int)points.size() == 3) return min(distance(points[0], points[1]), min(distance(points[0], points[2]),
distance(points[1], points[2]))); // 三个点
int mid = ((int)(points.size()) >> 1) - 1;
double d1, d2, d;
vector<point> left(mid + 1), right((int)points.size() - mid - 1);
copy(points.begin(), points.begin() + mid + 1, left.begin()); // 左边区域点集合
copy(points.begin() + mid + 1, points.end(), right.begin()); // 右边区域点集合
d1 = closest(left);
d2 = closest(right);
d = min(d1, d2);
return merge(points, d, mid);
}
int main(){
int count;
while(~scanf("%d", &count)){
if(count == 0) break;
vector<point> points;
double x, y;
for (int i = 0; i < count; ++i){
scanf("%lf%lf", &x, &y);
point p(x, y);
points.push_back(p);
}
sort(points.begin(), points.end(), cmp_x);
printf("%.2f
", closest(points)/2);
}
return 0;
}
/**
最近点对问题，时间复杂度为O(n*logn*logn)
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const double INF = 1e20;
const int N = 100005;
struct Point{
double x;
double y;
}point[N];
int n;
int tmpt[N];
bool cmpxy(const Point& a, const Point& b){
if(a.x != b.x)
return a.x < b.x;
return a.y < b.y;
}
bool cmpy(const int& a, const int& b){
return point[a].y < point[b].y;
}
double min(double a, double b){
return a < b ? a : b;
}
double dis(int i, int j){
return sqrt((point[i].x-point[j].x)*(point[i].x-point[j].x)
+ (point[i].y-point[j].y)*(point[i].y-point[j].y));
}
double Closest_Pair(int left, int right){
double d = INF;
if(left==right)
return d;
if(left + 1 == right)
return dis(left, right);
int mid = (left+right)>>1;
double d1 = Closest_Pair(left,mid);
double d2 = Closest_Pair(mid+1,right);
d = min(d1,d2);
int i,j,k=0;
//分离出宽度为d的区间
for(i = left; i <= right; i++){
if(fabs(point[mid].x-point[i].x) <= d)
tmpt[k++] = i;
}
sort(tmpt,tmpt+k,cmpy);
//线性扫描
for(i = 0; i < k; i++){
for(j = i+1; j < k && point[tmpt[j]].y-point[tmpt[i]].y<d; j++){
double d3 = dis(tmpt[i],tmpt[j]);
if(d > d3)
d = d3;
}
}
return d;
}
int main(){
while(true){
scanf("%d",&n);
if(n==0)
break;
for(int i = 0; i < n; i++)
scanf("%lf %lf",&point[i].x,&point[i].y);
sort(point,point+n,cmpxy);
printf("%.2lf
",Closest_Pair(0,n-1)/2);
}
return 0;
}