首页 > 其他分享 >平面最近点对 & 最小周长三角形 & 曼哈顿距离最近

平面最近点对 & 最小周长三角形 & 曼哈顿距离最近

时间：2024-10-07 09:22:47浏览次数：7  
标签：Right 周长 曼哈顿 rep mid pos int 最近 Left

Statement

求平面最近点对的距离，距离定义为欧几里德距离。

Solution

考虑按 \(x\) 排序，分治计算

先往左右递归，设得到的答案为 \(d\)，当前算跨过中点的答案，那么答案 \(\ge d\) 的点对可以不用枚举

设中点为 \(m\)

  • 对 \(i\in[l..m]\)，\(x_i\le x_m-d\) 的不用枚举；对 \(j\in[m+1..r]\)，\(x_j\ge x_m+d\) 的不用枚举
  • 对于所有 \(i\in[l..m]\)，不超过 6 个 \(j\in[m+1..r]\) 满足 \(x_j\in[x_m,x_m+d]\) 且 \(y_j\in[y_i-d,y_i+d]\)

于是对于需要枚举的点，按 \(y\) 排序，左边每个 \(i\) 枚举不超过 \(6\) 个候选点更新答案，\(O(n\log n)\)

Code

#include <bits/stdc++.h>
using namespace std;
#define rep(i, j, k) for (int i = (j); i <= (k); ++i)
#define reo(i, j, k) for (int i = (j); i >= (k); --i)
typedef long long ll;
const int N = 5e5 + 10;
struct Point {
	ll x, y;
} a[N], b[N];
int n;
ll ans;

ll dis(int u, int v) {
	return (a[u].x - a[v].x) * (a[u].x - a[v].x) + (a[u].y - a[v].y) * (a[u].y - a[v].y);
}
ll dis(Point u, Point v) {
	return (u.x - v.x) * (u.x - v.x) + (u.y - v.y) * (u.y - v.y);
}
void Solve(int l, int r) {
	if (r - l < 3) {
		rep(i, l, r) rep(j, i + 1, r) ans = min(ans, dis(i, j));
		sort(a + l, a + r + 1, [&](const Point& u, const Point& v) {
			return u.y < v.y;
		});
		return;
	}
	int mid = (l + r) >> 1;
	ll X = a[mid].x;
	Solve(l, mid), Solve(mid + 1, r);
	ll d = ceil(sqrt(ans));
	vector<Point> L, R;
	rep(i, l, mid)
		if (a[i].x > X - d) L.push_back(a[i]);
	rep(i, mid + 1, r)
		if (a[i].x < X + d) R.push_back(a[i]);
	int sz = R.size(), pl = 0, pr = 0;
	if (sz) {
		for (auto p : L) {
			while (pl < sz && R[pl].y < p.y - d) ++pl;
			while (pr < sz && R[pr].y <= p.y + d) ++pr;
			pr = max(pr - 1, 0);
			rep(i, pl, pr) ans = min(ans, dis(p, R[i]));
		}
	}
	for (int i = l, j = mid + 1, tot = l; i <= mid || j <= r; )
		if (i <= mid && (j > r || a[i].y <= a[j].y)) b[tot++] = a[i++];
		else b[tot++] = a[j++];
	rep(i, l, r) a[i] = b[i];
}

int main() {
	ios::sync_with_stdio(false), cin.tie(nullptr);
	cin >> n;
	rep(i, 1, n) {
		cin >> a[i].x >> a[i].y;
	}
	sort(a + 1, a + n + 1, [&](const Point& u, const Point& v) {
		return u.x < v.x;
	});
	ans = 1e18;
	Solve(1, n);
	cout << ans << '\n';
	return 0;
}

Statement

找出最小周长三角形的周长。为减小难度，这里三角形也包含共线的三点。

Solution

这里是距离 \(\ge\frac d2\) 的不用枚举，注意到这里候选点数同样是常数。

Code

#include <bits/stdc++.h>
using namespace std;
#define rep(i, j, k) for (int i = (j); i <= (k); ++i)
#define reo(i, j, k) for (int i = (j); i >= (k); --i)
typedef long long ll;
const int N = 2e5 + 10;
struct Point {
	double x, y;
} a[N];
int n;
double ans = 1e18;

double dis(int u, int v) {
	return sqrt(1.0 * (a[u].x - a[v].x) * (a[u].x - a[v].x) + 1.0 * (a[u].y - a[v].y) * (a[u].y - a[v].y));
}
double dis(Point u, Point v) {
	return sqrt(1.0 * (u.x - v.x) * (u.x - v.x) + 1.0 * (u.y - v.y) * (u.y - v.y));
}
void Solve(int l, int r) {
	if (r - l < 3) {
		if (r - l == 2) 
			ans = min(ans, dis(l, l + 1) + dis(l, l + 2) + dis(l + 1, l + 2));
		return;
	}
	int mid = (l + r) >> 1;
	Solve(l, mid), Solve(mid + 1, r);
	double d = ans / 2.0;
	vector<Point> L, R;
	rep(i, l, mid) 
		if (a[i].x >= a[mid].x - d) L.push_back(a[i]);
	rep(i, mid + 1, r)
		if (a[i].x <= a[mid].x + d) R.push_back(a[i]);
	sort(L.begin(), L.end(), [&](const Point& u, const Point& v) {
		return u.y < v.y;
	});
	sort(R.begin(), R.end(), [&](const Point& u, const Point& v) {
		return u.y < v.y;
	});
	int sz = R.size(), pl = 0, pr = 0;
	for (auto i : L) {
		while (pl < sz && R[pl].y < i.y - d) ++pl;
		while (pr < sz && R[pr].y <= i.y + d) ++pr;
		pr = max(0, pr - 1);
		if (pr - pl + 1 >= 2) 
			rep(u, pl, pr)
				rep(v, u + 1, pr) {
					ans = min(ans, dis(i, R[u]) + dis(i, R[v]) + dis(R[u], R[v]));
				}
	}
	sz = L.size(), pl = 0, pr = 0;
	for (auto i : R) {
		while (pl < sz && L[pl].y < i.y - d) ++pl;
		while (pr < sz && L[pr].y <= i.y + d) ++pr;
		pr = max(0, pr - 1);
		if (pr - pl + 1 >= 2) 
			rep(u, pl, pr)
				rep(v, u + 1, pr) {
					ans = min(ans, dis(i, L[u]) + dis(i, L[v]) + dis(L[u], L[v]));
				}
	}
}

int main() {
	ios::sync_with_stdio(false), cin.tie(nullptr);
	cin >> n;
	rep(i, 1, n) {
		cin >> a[i].x >> a[i].y;
	}
	sort(a + 1, a + n + 1, [&](const Point& u, const Point& v) {
		return u.x < v.x;
	});
	Solve(1, n);
	cout << fixed << setprecision(6) << ans << '\n';
	return 0;
}

Statement

  • 加点
  • 求曼哈顿距离与 \(u\) 最近的距离

Solution

问题等价于三维偏序

因为若 \(x_i\ge x,y_i\ge y\)，\(\min_{i}\{|x_i-x|+|y_i-y|\}=\min\{x_i+y_i-(x+y)\}=\min\{x_i+y_i\}-(x+y)\)

Code

#include <bits/stdc++.h>
using namespace std;
#define rep(i, j, k) for (int i = (j); i <= (k); ++i)
#define reo(i, j, k) for (int i = (j); i >= (k); --i)
typedef long long ll;
const int N = 3e6 + 10;
struct Oper {
	int op, x, y, id;
} a[N], b[N], c[N];
int n, m, tot, qtot, ans[N];

struct BIT {
	int mn[N];
	BIT() {
		rep(i, 0, N - 1) mn[i] = 1e9;
	}
	void Upd(int x, int v) {
		for (; x < N; x += x & -x) mn[x] = min(mn[x], v);
	}
	int Qry(int x) {
		int res = 1e9;
		for (; x; x -= x & -x) res = min(res, mn[x]);
		return res;
	}
	void Clear(int x) {
		for (; x < N; x += x & -x) mn[x] = 1e9;
	}
} bit;

void Solve1(int l, int r) {
	if (l == r) return;
	int mid = (l + r) >> 1;
	Solve1(l, mid), Solve1(mid + 1, r);
	vector<Oper> Left, Right;
	rep(i, l, mid) 
		if (b[i].op == 1) Left.push_back(b[i]);
	rep(i, mid + 1, r)
		if (b[i].op == 2) Right.push_back(b[i]);
	int pos = Left.size();
	reo(i, (int)Right.size() - 1, 0) {
		while (pos && Left[pos - 1].x >= Right[i].x) 
			--pos, bit.Upd(N - Left[pos].y, Left[pos].x + Left[pos].y);
		ans[Right[i].id] = min(ans[Right[i].id], bit.Qry(N - Right[i].y) - (Right[i].x + Right[i].y));
	}
	rep(i, pos, (int)Left.size() - 1) bit.Clear(N - Left[i].y);
	int R = l - 1;
	for (int i = l, j = mid + 1; i <= mid || j <= r; )
		if (i <= mid && (j > r || b[i].x <= b[j].x)) c[++R] = b[i++];
		else c[++R] = b[j++];
	rep(i, l, r) b[i] = c[i];
}

void Solve2(int l, int r) {
	if (l == r) return;
	int mid = (l + r) >> 1;
	Solve2(l, mid), Solve2(mid + 1, r);
	vector<Oper> Left, Right;
	rep(i, l, mid)
		if (b[i].op == 1) Left.push_back(b[i]);
	rep(i, mid + 1, r)
		if (b[i].op == 2) Right.push_back(b[i]);
	int pos = Left.size();
	reo(i, (int)Right.size() - 1, 0) {
		while (pos && Left[pos - 1].x >= Right[i].x) 
			--pos, bit.Upd(Left[pos].y, Left[pos].x - Left[pos].y);
		ans[Right[i].id] = min(ans[Right[i].id], bit.Qry(Right[i].y) - (Right[i].x - Right[i].y));
	}
	rep(i, pos, (int)Left.size() - 1) bit.Clear(Left[i].y);
	int R = l - 1;
	for (int i = l, j = mid + 1; i <= mid || j <= r; )
		if (i <= mid && (j > r || b[i].x <= b[j].x)) c[++R] = b[i++];
		else c[++R] = b[j++];
	rep(i, l, r) b[i] = c[i];
}

void Solve3(int l, int r) {
	if (l == r) return;
	int mid = (l + r) >> 1;
	Solve3(l, mid), Solve3(mid + 1, r);
	vector<Oper> Left, Right;
	rep(i, l, mid)
		if (b[i].op == 1) Left.push_back(b[i]);
	rep(i, mid + 1, r)
		if (b[i].op == 2) Right.push_back(b[i]);
	int pos = -1;
	rep(i, 0, (int)Right.size() - 1) {
		while (pos < (int)Left.size() - 1 && Left[pos + 1].x <= Right[i].x)
			++pos, bit.Upd(Left[pos].y, - Left[pos].x - Left[pos].y);
		ans[Right[i].id] = min(ans[Right[i].id], Right[i].x + Right[i].y + bit.Qry(Right[i].y));
	}
	rep(i, 0, pos) bit.Clear(Left[i].y);
	int R = l - 1;
	for (int i = l, j = mid + 1; i <= mid || j <= r; )
		if (i <= mid && (j > r || b[i].x <= b[j].x)) c[++R] = b[i++];
		else c[++R] = b[j++];
	rep(i, l, r) b[i] = c[i];
}

void Solve4(int l, int r) {
	if (l == r) return;
	int mid = (l + r) >> 1;
	Solve4(l, mid), Solve4(mid + 1, r);
	vector<Oper> Left, Right;
	rep(i, l, mid)
		if (b[i].op == 1) Left.push_back(b[i]);
	rep(i, mid + 1, r)
		if (b[i].op == 2) Right.push_back(b[i]);
	int pos = -1;
	rep(i, 0, (int)Right.size() - 1) {
		while (pos < (int)Left.size() - 1 && Left[pos + 1].x <= Right[i].x)
			++pos, bit.Upd(N - Left[pos].y, Left[pos].y - Left[pos].x);
		ans[Right[i].id] = min(ans[Right[i].id], Right[i].x - Right[i].y + bit.Qry(N - Right[i].y));
	}
	rep(i, 0, pos) bit.Clear(N - Left[i].y);
	int R = l - 1;
	for (int i = l, j = mid + 1; i <= mid || j <= r; )
		if (i <= mid && (j > r || b[i].x <= b[j].x)) c[++R] = b[i++];
		else c[++R] = b[j++];
	rep(i, l, r) b[i] = c[i];
}

int main() {
	ios::sync_with_stdio(false), cin.tie(nullptr);
	cin >> n >> m;
	rep(i, 1, n) 
		++tot, a[tot].op = 1, cin >> a[tot].x >> a[tot].y;
	rep(i, 1, m) {
		++tot, cin >> a[tot].op >> a[tot].x >> a[tot].y;
		if (a[tot].op == 2) 
			a[tot].id = ++qtot;
	}
	rep(i, 1, qtot) ans[i] = 2e9;
	rep(i, 1, tot) b[i] = a[i];
	Solve1(1, tot);
	rep(i, 1, tot) b[i] = a[i];
	Solve2(1, tot);
	rep(i, 1, tot) b[i] = a[i];
	Solve3(1, tot);
	rep(i, 1, tot) b[i] = a[i];
	Solve4(1, tot);
	rep(i, 1, qtot) cout << ans[i] << '\n';
	return 0;
}

注意到 K-D Tree 直接秒了。

标签：Right,周长,曼哈顿,rep,mid,pos,int,最近,Left
From： https://www.cnblogs.com/laijinyi/p/18449772

相关文章

  • 帝国cms会员空间模板显示最近来访访客信息
    为了实现用户登录状态下的信息记录以及未登录状态下的IP地区记录功能，你可以按照以下步骤操作：第一步：创建数据表在帝国CMS后台执行以下SQL语句创建数据表：CREATETABLE`{$dbtbpre}_userkjf`(`id`int(11)NOTNULLAUTO_INCREMENT,`lfuserid`varchar(20)CHARACTERSE......
  • 最近对问题
    设p1=(x1,y1),p2=(x2,y2),⋯,pn=(xn,yn)是平面上n个点构成的集合S,设计算法找出集合S中距离最近的点对。蛮力法初始化最小距离：首先，将最小距离 minDist 初始化为正无穷大（+∞），表示当前还没有找到任何点对。双重循环遍......
  • 2289 马拉松 暴力枚举 曼哈顿距离
    解决思路 计算总距离：首先计算贝茜不跳过任何检查点的总行进距离。 尝试跳过每个检查点：对于每个可以跳过的检查点，计算跳过该检查点后的行进距离，并记录最小的行进距离。 输出结果：输出最小的行进距离。#include<bits/stdc++.h>#definelllonglongusingnamespac......
  • 线性平面最近点对
    讲述一种期望线性复杂度的平面最近点对算法。将点打乱对于小常数\(D\)，暴力计算前\(D\)个点的平面最近点对。考虑从前\(i-1\)个点推出前\(i\)个点的平面最近点对：设前\(i-1\)个点的平面最近点对距离为\(s\)，将平面以\(s\)为边长划分成若干网格，用哈希表记录每个网格......
  • 平面最近点对
    #include<bits/stdc++.h>usingnamespacestd;constintN=2e5+5,inf=0x7f7f7f7f;intn;structPoint{doublex,y;}a[N],t[N];boolcmp1(PointA,PointB){if(A.x==B.x)returnA.y<B.y;returnA.x<B.x;}boolcmp2(PointA,PointB){......
  • 8，(经典面试题:分组求topN)Python数分之Pandas训练，力扣，1532. 最近的三笔订单
    学习：知识的初次邂逅复习：知识的温故知新练习：知识的实践应用目录一，原题力扣链接二，题干三，建表语句四，分析五，Pandas解答六，验证七，知识点总结一，原题力扣链接.-力扣（LeetCode）二，题干表：Customers+---------------+---------+|ColumnName|Type|+------......
  • 最近公共祖先思考题
    #1有n个物品，每个物品有重量wi和体积vi且密度均匀。你可以切物品，每次可以选一个物品切成两部分，也就是选一个0到1的实数k把物品分成k和(1-k)比例的两个物品。你有最多X次切的机会。问题1.要想保证切完之后一定能把物品分成两组使得两组重量和相等，体积和也相等，X至少是几。ans1.......
  • 道歉贴，为最近写的一篇“垃圾贴”
    最近写了几篇阅读量高的文章,其实说到阅读量特别的高,我并怎么不高兴,到这里一定有人说,你装,装什么B!我写现在这篇文章的时候是2024年9月14日,显示的是这三篇文章,当时的阅读量,让我最不开心或者说郁闷的是第一篇,Oracle的那篇。Why，因为我自己认为，那篇文章垃圾,太垃圾了,我作......
  • 为什么多模态大语言模型最近用BLIP2中Q-Former结构的变少了？
    前言本篇介绍为什么多模态大语言模型（MLLM）最近的工作中用BLIP2中Q-Former结构的变少了？简单来说，相较于MLP的方案，即LLaVA-1.5，BLIP-2中的Q-Former模型在参数量上更为庞大，其收敛过程也相对缓慢。在同等条件下，Q-Former的性能并未达到LLaVA-1.5所展现出的卓越水平。值得注意的是，即使在数据......
  • 463. 岛屿的周长
    思路一个陆地的周长为4如果这个陆地上、下、左、右有陆地相连，则这个岛屿的周长=4-相邻陆地的边的长度classSolution(object):defislandPerimeter(self,grid):""":typegrid:List[List[int]]:rtype:int"""row=le......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99