专门做招商的网站是什么意思,广州设计公司网站,营销策划有限公司经营范围,网站首页生成静态页面平面最近点对#xff08;加强加强版#xff09;
题目背景
P1429 平面最近点对#xff08;加强版#xff09;里最高赞题解写道#xff1a; 我们充分发扬人类智慧#xff1a; 将所有点全部绕原点旋转同一个角度#xff0c;然后按 x x x 坐标排序 根据数学直觉#xff…平面最近点对加强加强版
题目背景
P1429 平面最近点对加强版里最高赞题解写道 我们充分发扬人类智慧 将所有点全部绕原点旋转同一个角度然后按 x x x 坐标排序 根据数学直觉在随机旋转后答案中的两个点在数组中肯定不会离得太远 所以我们只取每个点向后的 5 5 5 个点来计算答案 这样速度快得飞起在 n 1000000 n1000000 n1000000 时都可以在 1 s 内卡过 当然这是错的。
题目描述
给定 n n n 个二维欧几里得平面上的点 p 1 , p 2 , … , p n p_1, p_2, \dots, p_n p1,p2,…,pn请输出距离最近的两个点的距离。
输入格式
输入第一行为一个正整数 n n n表示点数。
接下来 n n n 行第 i i i 行为用空格隔开的整数 x i , y i x_i, y_i xi,yi表示 p i ( x i , y i ) p_i (x_i, y_i) pi(xi,yi)。
输入保证没有两个坐标完全相同的点。
输出格式
输出一行包含一个整数 D 2 D^2 D2表示距离最近的两个点的距离的平方。
由于输入的点为整点因此这个值一定是整数。
样例 #1
样例输入 #1
2
-10000000 -10000000
10000000 10000000样例输出 #1
800000000000000样例 #2
样例输入 #2
5
1 1
1 9
9 1
9 9
0 10样例输出 #2
2提示
对于第二组样例 ( 1 , 9 ) (1, 9) (1,9)、 ( 0 , 10 ) (0, 10) (0,10) 两个点最近距离为 2 \sqrt 2 2 因此你需要输出 2 2 2。
数据范围
对于 100 % 100 \% 100% 的数据 2 ≤ n ≤ 4 × 1 0 5 2 \leq n \leq 4 \times 10^5 2≤n≤4×105 − 1 0 7 ≤ x i , y i ≤ 1 0 7 -10^7 \leq x_i, y_i \leq 10^7 −107≤xi,yi≤107。
本题目标复杂度是 O ( n log 2 n ) O(n \log ^2 n) O(nlog2n)。设置 350ms 时限的原因是 O ( n log 2 n ) O(n \log ^2 n) O(nlog2n) 参考代码使用 cin 不会 TLE。最快的 std 能 100ms。wlzhouzhuan 的程序能恰好在 350ms 内跑 1000 n 1000n 1000n 次检查。150 组测试数据为了防止卡评测。
分析
典型分治题我们二分求解会得到左右两侧的最小值考虑跨越中心线时的答案其横纵坐标差均小于d才可能为正确答案
代码
#include bits/stdc.h
using namespace std;
const int M4*1e510;
#define int long long
pairint,int a[M];
int n;
int d1e16;
pairint,int vl[M],vr[M];
void read(){ios::sync_with_stdio(false);cinn;for (int i1;in;i)cina[i].firsta[i].second;
}
int dis2(pairint,int a,pairint,int b){return (a.first - b.first) * (a.first - b.first) 1ll * (a.second - b.second) * (a.second - b.second);
}
void solve(int l,int r){if (lr){swap(a[l].first,a[l].second);return;}int midlr1;int xa[mid].first;solve(l,mid);solve(mid1,r);double dissqrt(d);int sl0,sr0;for (int il;imid;i)if (x-a[i].seconddis) vl[sl]a[i];for (int imid1;ir;i)if(a[i].second-xdis) vr[sr]a[i];int p1,q0;for (int i1;isl;i){while(psr and vl[i].first-vr[p].firstdis) p;while(qsr and vr[q1].first-vl[i].firstdis) q;for (int jp;jq;j) dmin(d,dis2(vl[i],vr[j]));}inplace_merge(al,amid1,ar1);
}
signed main() {read();sort(a1,an1);solve(1,n);coutdendl;return 0;
}分析 if (lr){swap(a[l].first,a[l].second);return;}翻转pair的first与second,便于按y排序
for (int il;imid;i)if (x-a[i].seconddis) vl[sl]a[i];for (int imid1;ir;i)if(a[i].second-xdis) vr[sr]a[i];选取在x上符合要求的点
for (int i1;isl;i){while(psr and vl[i].first-vr[p].firstdis) p;while(qsr and vr[q1].first-vl[i].firstdis) q;for (int jp;jq;j) dmin(d,dis2(vl[i],vr[j]));}选取在y上符合要求的点
inplace_merge(al,amid1,ar1);选完后方便上一层调用使用归并
