首页 > 其他分享 >P1429&&P7883 平面最近点对(加强版 && 加强加强版)

P1429&&P7883 平面最近点对(加强版 && 加强加强版)

时间:2024-02-17 20:57:28浏览次数:34  
标签:ch 加强版 int P7883 long 最小值 &&

这是一道非常经典的题目。

首先可以想到暴力的算法,一一匹配取最小值,期望时间复杂度为 $O(n^2)$,很明显过不了此题。

所以我们考虑分治,我们每次将所有点按 x 分为两半,然后分治两半,取最小值,然后就可以获取到左右两块内部最小值,那么大范围内的最小值只有左边最小值,右边最小值或者横跨左右的最小值。我们假设d=min(左边,右边)那么易得横跨左右的最小值中左右端点肯定在 $x\in[x_{mid} - d,x_{mid} + d]$ 的点之间。那么我们取出所有符合的点后按 y 排序,就暴力合并左右,显然对于每个点 i,只要考虑取出的点中 $y\in[y_i, y_i + d]$ 的点就好了。

暴力看起来慢,但是实际上可以证明对于每个点只有很少的点符合这个值(虽然我不会)

因为 sqrt 为浮点数,所有为保证精度,我就将所有距离的平方值存了下来,然而要注意寻找符合范围的点要以 sqrt 值为标准。

#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 4e5 + 5;
const long long inf = 9e18;
struct node {
    long long x, y;
}no[N], tmp[N];
int n;
inline long long read(){
	long long w = 1, s = 0;
	char ch = getchar();
	while(ch < '0' || ch > '9'){
		if(ch == '-') w = -w;
		ch = getchar();
	}
	while(ch >= '0' && ch <= '9'){
		s = (s<<3) + (s<<1) + (ch^48);
		ch = getchar();
	}
	return w * s;
}
bool cmp(node a, node b) {
    return a.x == b.x ? a.y < b.y : a.x < b.x;
}
bool cmp1(node a, node b) {
    return a.y < b.y;
}
long long dist(node i, node j) {
    return (i.x - j.x) * (i.x - j.x) + (i.y - j.y) * (i.y - j.y);
}
long long merge(int l, int r) {
    if (l == r) return inf;
    if (r == l + 1) return dist(no[l], no[r]);
    int mid = l + r >> 1;
    long long ans = min(merge (l, mid), merge (mid + 1, r)), tmpp;
    double ttmp = sqrt(ans);
    int cnt = 0;
    for (int i = l;i <= r; ++ i)
        if (abs (no[i].x - no[mid].x) < ttmp)
            tmp[++ cnt] = no[i];
    sort (tmp + 1, tmp + cnt + 1, cmp1);
    for (int i = 1;i < cnt; ++ i)
        for (int j = i + 1;j <= cnt && tmp[j].y < tmp[i].y + ttmp; ++ j) {
            tmpp = dist(tmp[i], tmp[j]);
            if (tmpp < ans)
                ans = tmpp;
        }
    return ans;
}
int main() {
    scanf ("%d", &n);
    for (int i = 1;i <= n; ++ i) {
        no[i].x = read();
        no[i].y = read();
    }
    sort (no + 1, no + n + 1, cmp);
    // printf ("%lld", merge (1, n)); // 加强加强版输出
    printf ("%.4lf", sqrt (merge (1, n))); // 加强版输出
    return 0;
}

标签:ch,加强版,int,P7883,long,最小值,&&
From: https://www.cnblogs.com/Assassins-Creed/p/18018375

相关文章

  • 【题解】P4722 【模板】最大流 加强版 / 预流推进
    更好阅读体验CHAPTER0废话1.常见的最大流算法可以大致分为两种:找增广路和预流推进2.从理论时间复杂度上界来看,找增广路算法的最坏时间复杂度为\(O(n^2m)\),而预流推进算法的最坏时间复杂度为\(O(n^2\sqrt{m})\),看起来预流推进要显然优于找增广路,但在实际应用(尤指OI)中,由于包......
  • P2241 统计方形(数据加强版)
    统计方形(数据加强版)题目背景1997年普及组第一题题目描述有一个\(n\timesm\)方格的棋盘,求其方格包含多少正方形、长方形(不包含正方形)。输入格式一行,两个正整数\(n,m\)(\(n\leq5000,m\leq5000\))。输出格式一行,两个正整数,分别表示方格包含多少正方形、长方形(不包含正......
  • P8786 [蓝桥杯 2022 省 B] 李白打酒加强版
    原题链接题解根据样例,观察到李白总共走\(n+m\)次,每一次不是遇到酒馆就是遇到花故我们可以设\(dp[i][0/1]\)代表第\(i\)次遇到酒馆或花的方案数但是我们发现这样的状态不好转移故我们可以设\(dp[i][0/1][k]\)代表第\(i\)次遇到酒馆或花,还剩下\(k\)斗酒的方案数但......
  • 【题解】P5907 数列求和加强版 / P4948 数列求和
    本题解是对warzone的题解的补充。题意:求\[\sum_{i=1}^ni^ka^i\]普通版:\(k\leq2\times10^3\)。加强版:\(k\leq10^7\)。首先先考虑普通版。\[\begin{aligned}\sum_{i=1}^ni^ka^i&=\sum_{i=1}^na^i\sum_{j=0}^k{k\bracej}i^{\underline{j}}\\&=\sum_{j=0......
  • 洛谷P5907 数列求和加强版 / SPOJ MOON4
    题面描述求\[\sum_{i=1}^ni^ka^i\]对\(998244353\)取模的结果。\(O(k)\)做法为了推导方便,下令\(p=a^{-1}\)。即求\[\sum_{i=1}^n\frac{i^k}{p^i}\]我们裂项,即尝试寻找多项式\(f(x)\),使得\[\frac{x^k}{p^x}=\frac{f(x)}{p^{x-1}}-\frac{f(x+1)}{p^x}\]即\[x^k......
  • 洛谷题单指南-暴力枚举-P2241 统计方形(数据加强版)
    原题链接:https://www.luogu.com.cn/problem/P2241题意解读:要在整个n*m区域计算正方形和长方形的个数,枚举法即可。解题思路:此题枚举的对象是矩形的高i和宽j,高的范围[1,n],宽的范围[1,m],然后计算在n*m区域内有多少个i*j,i==j即属于正方形,i!=j属于长方形。那么,问题就集中在了......
  • 通达信行业板块看盘加强版指标公式源码
    创业板:=INBLOCK('创业板');中小企业:=INBLOCK('中小板');上证A股:=INBLOCK('上证A股');深证A股:=INBLOCK('深证A股');INDEH:=IF(中小企业=1,"399005$H",IF(创业板=1,"399006$H",IF(上证A股=1,"999999$H","399001$H"))),NOD......
  • P2045 方格取数加强版题解
    题目链接:P2045方格取数加强版-洛谷|计算机科学教育新生态(luogu.com.cn)题目:出一个n*n的矩阵,每一格有一个非负整数A{i,j}且A{i,j} <=10^3现在从(1,1)出发,可以往右或者往下走,最后到达(n,n),每达到一格,把该格子的数取出来,该格子的数就变成0,这样一共走K次,现在要......
  • 操作序列计数加强加强加强加强版(polylog)
    哎跟风发一下。前边的工作类似,设\(F_i(x)\)表示从高到低考虑到了第\(i\)位,且第\(i\)位向下退\(x\)的方案数,其中初值为\(F_0(x)=1\),根据转移可以归纳出这是一个\(i\)次多项式。然后就有经典的插值做法,可以做到\(O(n^3)\),但是不够strong,考虑不去维护点值,而是维护系数......
  • 南外集训 2024.1.12 T3/AGC022F Checkers 加强版
    第一步转化比较套路,DP设计需要很强的洞察力,最后的优化也很考验基本功。有\(n\)个\(n\)维空间中的点,第\(i\)个点\(x_i\)满足\(x_{i,i}=1,x_{i,j}=0(\foralli\neqj)\)。接下来进行\(n-1\)次操作,每次任选两个点,将第一个点关于第二个点对称,然后删掉第二个点。......