【hdoj 1007】最近點對
來源：程序員人生 發布時間：2015-05-19 08:01:36 閱讀次數：2856次
題目：傳送門
解答：直接暴力求解肯定會超時。此題核心就是求出來最近的1對點之間的距離，即最近點對算法。
扼要來講就是利用分治的思想，左半邊的最小距離，與右半邊的最小距離比較，得到1個mindist。再遍歷分界限左右 mindist 范圍內點的間距，取最小值。
這樣，需要暴力的只有分界限周圍的點。但是我第1次提交版本還是超時。詢問以后是由于優化不夠，寫在trick中。
這里1些trick:
- 分界限：不1定是距離上的等分，根據 x 軸位置排序落后行數量上的等分（取最中間的點）左右更好；
- 取中點暴力時，切記不要與本身比較（距離為0）；
- 除非有 string，不然不要用 cin，scanf 會快上很多；
- 這個我1直很想吐槽……數據精度，做 oj 就別用 float 了，直接上 double（困擾我好久）；
- 浮點數（float，double）是不存在完全相等的（參見這里）。可以用eps（1般為1e⑹, 1e⑻），利用 fabs（abs是整數取絕對值）判斷范圍是不是小于 eps.
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <math.h>
#include <string>
#include <string.h>
#define MAXDIST 1000000
using namespace std;
struct Point{
double x;
double y;
};
int n;
double x, y;
bool tag;
Point tmp;
double eps = 1e⑻;
Point gao[100005];
bool cmpxy (const Point a, const Point b)
{
if(a.x != b.x)
{
return a.x < b.x;
}
else
{
return a.y < b.y;
}
}
bool cmpx (const Point a, const Point b)
{
return a.x < b.x;
}
bool cmpy (const Point a, const Point b)
{
return a.y < b.y;
}
double dist(const Point a, const Point b)
{
return ((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
double nearestPair(int head, int tail)
{
if(head == tail)
{
return MAXDIST;
}
if(head + 1 == tail)
{
return dist(gao[head], gao[tail]);
}
int mid = (head + tail) >> 1;
double d1 = nearestPair(head, mid);
double d2 = nearestPair(mid + 1, tail);
double mindist = d1 > d2 ? d2 : d1;
for(int i = head; i<=tail; i++)
{
// 不能和本身比較，否則距離為 0
if(i != mid && gao[i].x > (gao[mid].x - mindist) && gao[i].x < (gao[mid].x + mindist))
{
if(dist(gao[i], gao[mid]) < mindist)
mindist = dist(gao[i], gao[mid]);
}
}
return mindist;
}
int main()
{
while(cin>>n && n!= 0)
{
memset(gao, 0, sizeof(gao));
tag = false;
for(int i=0; i<n; i++)
{
scanf("%lf%lf", &x, &y);
tmp.x = x;
tmp.y = y;
gao[i] = tmp;
}
sort(gao, gao + n, cmpxy);
for(int i=0; i < n⑴; i++)
{
if(fabs(gao[i].x - gao[i+1].x) < eps && fabs(gao[i].y - gao[i+1].y) < eps)
tag = true;
}
if(tag)
{
cout<<"0.00"<<endl;
continue;
}
else
{
double d = nearestPair(0, n⑴);
printf("%.2f
", sqrt(d)/2);
}
}
return 0;
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
