題意:
? ? ? 給你n個點,讓你求最近的兩個點的距離是多少.
思路:

? ? ? 這個題目我沒思路,我在網上看的是什么分治 + 鴿巢原理,分治我知道,鴿巢原理我也知道,但是這個題目就是沒有證明出來他和鴿巢原理有jm關系,總之就是先以x或者y優先sort一下,然后每次枚舉每個相鄰點的附近5個就行了(加自己一共六個),而且這個題目的前提好像還是什么數據必須是隨機產生的吧,ac可以,但不明白..

#include<stdio.h> #include<math.h> #include<algorithm>#define N 100000 + 100 using namespace std;typedef struct {double x ,y; }NODE;NODE node[N];bool camp(NODE a ,NODE b) {return a.y < b.y || a.y == b.y && a.x < b.x; }double dis(NODE a ,NODE b) {return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y); }int main () {int n ,i ,j;while(~scanf("%d" ,&n) && n){for(i = 1 ;i <= n ;i ++)scanf("%lf %lf" ,&node[i].x ,&node[i].y);sort(node + 1 ,node + n + 1 ,camp);double min = 1000000000;for(i = 1 ;i <= n ;i ++)for(j = i + 1 ;j <= i + 5 && j <= n ;j ++){double now = dis(node[i] ,node[j]);if(min > now) min = now;}printf("%.2lf\n" ,sqrt(min)/2);}return 0; }

總結

以上是生活随笔為你收集整理的hdu1007 最近点对的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。