題意：S是平面內點的集合，初始為空，每次向集合里面加入一個點P(x,y)，詢問S內最近點對的距離的平方和

思路：設當前集合的答案為D，則找到集合里面橫坐標在(x-√D,x+√D)內的數，用它們來更新答案，一邊更新答案一邊還要更新右邊界x+√D，此時的更新注意不要用浮點數開平方算具體右邊界，改用判斷即可，否則超時。

?

123456789 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85

#include <map> #include <set> #include <cmath> #include <ctime> #include <deque> #include <queue> #include <stack> #include <vector> #include <cstdio> #include <string> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm>using namespace std;#define X first #define Y second #define pb push_back #define mp make_pair #define all(a) (a).begin(), (a).end() #define fillchar(a, x) memset(a, x, sizeof(a)) #define copy(a, b) memcpy(a, b, sizeof(a))typedef long long ll; typedef pair<int, int> pii; typedef unsigned long long ull;//#ifndef ONLINE_JUDGE void RI(vector<int>&a,int n){a.resize(n);for(int i=0;i<n;i++)scanf("%d",&a[i]);} void RI(){}void RI(int&X){scanf("%d",&X);}template<typename...R> void RI(int&f,R&...r){RI(f);RI(r...);}void RI(int*p,int*q){int d=p<q?1:-1; while(p!=q){scanf("%d",p);p+=d;}}void print(){cout<<endl;}template<typename T> void print(const T t){cout<<t<<endl;}template<typename F,typename...R> void print(const F f,const R...r){cout<<f<<", ";print(r...);}template<typename T> void print(T*p, T*q){int d=p<q?1:-1;while(p!=q){cout<<*p<<", ";p+=d;}cout<<endl;} //#endif template<typename T>bool umax(T&a, const T&b){return b<=a?false:(a=b,true);} template<typename T>bool umin(T&a, const T&b){return b>=a?false:(a=b,true);} template<typename T> void V2A(T a[],const vector<T>&b){for(int i=0;i<b.size();i++)a[i]=b[i];} template<typename T> void A2V(vector<T>&a,const T b[]){for(int i=0;i<a.size();i++)a[i]=b[i];}const double PI = acos(-1.0); const int INF = 1e9 + 7; const double EPS = 1e-8;/* -------------------------------------------------------------------------------- */multiset<pii> S;int main() { #ifndef ONLINE_JUDGEfreopen("in.txt", "r", stdin);//freopen("out.txt", "w", stdout); #endif // ONLINE_JUDGEint T, n, ax, bx, cx, ay, by, cy, x, y;cin >> T;while (T --) {scanf("%d%d%d%d%d%d%d", &n, &ax, &bx, &cx, &ay, &by, &cy);S.clear();x = bx % cx;y = by % cy;S.insert(mp(x, y));ll ans = 0, mind = (ll)INF * INF;for (int i = 1; i < n; i ++) {x = ((ll)x * ax + bx) % cx;y = ((ll)y * ay + by) % cy;int dx = (int)(sqrt(mind * 1.0) + 1);multiset<pii>::iterator iter = S.lower_bound(mp(x - dx, -INF));for (; iter != S.end(); iter ++) {ll X = (*iter).X - x, Y = (*iter).Y - y;ll buf = X * X + Y * Y;if (X >= 0 && X * X >= mind) break;umin(mind, buf);}ans += mind;S.insert(mp(x, y));}cout << ans << endl;}return 0; }

轉載于:https://www.cnblogs.com/jklongint/p/4724632.html

總結

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

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