- Java 双重比较
- java - 比较器与 Apache BeanComparator
- Objective-C 完成 block 导致额外的方法调用?
- database - RESTful URI 是否应该公开数据库主键?
我试图在 Manhattan metric 中找到最小距离(x,y)。我正在搜索有关此的信息。但我还没有找到任何东西。
#include<bits/stdc++.h>
using namespace std;
#define st first
#define nd second
pair<int, int> pointsA[1000001];
pair<int, int> pointsB[1000001];
int main() {
int n, t;
unsigned long long dist;
scanf("%d", &t);
while(t-->0) {
dist = 4000000000LL;
scanf("%d", &n);
for(int i = 0; i < n; i++) {
scanf("%d%d", &pointsA[i].st, &pointsA[i].nd);
}
for(int i = 0; i < n; i++) {
scanf("%d%d", &pointsB[i].st, &pointsB[i].nd);
}
for(int i = 0; i < n ;i++) {
for(int j = 0; j < n ; j++) {
if(abs(pointsA[i].st - pointsB[j].st) + abs(pointsA[i].nd - pointsB[j].nd) < dist) {
dist = abs(pointsA[i].st - pointsB[j].st) + abs(pointsA[i].nd - pointsB[j].nd);
}
}
printf("%lld\n", dist);
}
}
}
我的代码在 O(n^2) 中运行但速度太慢。我不知道它是否有用,但 pointsA 中的 y 总是 > 0,pointB 中的 y 总是 < 0。我的代码实际比较距离到下一个并选择最小的。
例如:
输入:
2
3
-2 2
1 3
3 1
0 -1
-1 -2
1 -2
1
1 1
-1 -1
输出:
5
4
最佳答案
我的解决方案(为简单起见,我不关心 manhattan_dist
中的溢出,因此它不适用于 unsigned long long
):
#include <cstdlib>
#include <cstdio>
#include <cassert>
#include <vector>
#include <limits>
#include <algorithm>
typedef std::pair<int, int> Point;
typedef std::vector<std::pair<int, int> > PointsList;
static inline bool cmp_by_x(const Point &a, const Point &b)
{
if (a.first < b.first) {
return true;
} else if (a.first > b.first) {
return false;
} else {
return a.second < b.second;
}
}
static inline bool cmp_by_y(const Point &a, const Point &b)
{
if (a.second < b.second) {
return true;
} else if (a.second > b.second) {
return false;
} else {
return a.first < b.first;
}
}
static inline unsigned manhattan_dist(const Point &a, const Point &b)
{
return std::abs(a.first - b.first) +
std::abs(a.second - b.second);
}
int main()
{
unsigned int n_iter = 0;
if (scanf("%u", &n_iter) != 1) {
std::abort();
}
for (unsigned i = 0; i < n_iter; ++i) {
unsigned int N = 0;
if (scanf("%u", &N) != 1) {
std::abort();
}
if (N == 0) {
continue;
}
PointsList pointsA(N);
for (PointsList::iterator it = pointsA.begin(), endi = pointsA.end(); it != endi; ++it) {
if (scanf("%d%d", &it->first, &it->second) != 2) {
std::abort();
}
assert(it->second > 0);
}
PointsList pointsB(N);
for (PointsList::iterator it = pointsB.begin(), endi = pointsB.end(); it != endi; ++it) {
if (scanf("%d%d", &it->first, &it->second) != 2) {
std::abort();
}
assert(it->second < 0);
}
std::sort(pointsA.begin(), pointsA.end(), cmp_by_y);
std::sort(pointsB.begin(), pointsB.end(), cmp_by_y);
const PointsList::const_iterator min_a_by_y = pointsA.begin();
const PointsList::const_iterator max_b_by_y = (pointsB.rbegin() + 1).base();
assert(*max_b_by_y == pointsB.back());
unsigned dist = manhattan_dist(*min_a_by_y, *max_b_by_y);
const unsigned diff_x = std::abs(min_a_by_y->first - max_b_by_y->first);
const unsigned best_diff_y = dist - diff_x;
const int max_y_for_a = max_b_by_y->second + dist;
const int min_y_for_b = min_a_by_y->second - dist;
PointsList::iterator it;
for (it = pointsA.begin() + 1; it != pointsA.end() && it->second <= max_y_for_a; ++it) {
}
if (it != pointsA.end()) {
pointsA.erase(it, pointsA.end());
}
PointsList::reverse_iterator rit;
for (rit = pointsB.rbegin() + 1; rit != pointsB.rend() && rit->second >= min_y_for_b; ++rit) {
}
if (rit != pointsB.rend()) {
pointsB.erase(pointsB.begin(), (rit + 1).base());
}
std::sort(pointsA.begin(), pointsA.end(), cmp_by_x);
std::sort(pointsB.begin(), pointsB.end(), cmp_by_x);
for (size_t j = 0; diff_x > 0 && j < pointsA.size(); ++j) {
const Point &cur_a_point = pointsA[j];
assert(max_y_for_a >= cur_a_point.second);
const int diff_x = dist - best_diff_y;
const int min_x = cur_a_point.first - diff_x + 1;
const int max_x = cur_a_point.first + diff_x - 1;
const Point search_term = std::make_pair(max_x, std::numeric_limits<int>::min());
PointsList::const_iterator may_be_near_it = std::lower_bound(pointsB.begin(), pointsB.end(), search_term, cmp_by_x);
for (PointsList::const_reverse_iterator rit(may_be_near_it); rit != pointsB.rend() && rit->first >= min_x; ++rit) {
const unsigned cur_dist = manhattan_dist(cur_a_point, *rit);
if (cur_dist < dist) {
dist = cur_dist;
}
}
}
printf("%u\n", dist);
}
}
我机器上的基准测试(Linux + i7 2.70 GHz + gcc -Ofast -march=native):
$ make bench
time ./test1 < data.txt > test1_res
real 0m7.846s
user 0m7.820s
sys 0m0.000s
time ./test2 < data.txt > test2_res
real 0m0.605s
user 0m0.590s
sys 0m0.010s
test1
是你的变体,test2
是我的。
关于c++ - 曼哈顿度量中的最小距离,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/39183668/
A是不同元素的序列,B是A的子序列,A-B是A中的所有元素,但不是B中的所有元素距离(A) = 总和|a(i)-a(i+1)|从 i=1 到 n-1找到一个子序列 B 使得 Dist(B)+Dist(
我想通过计算每对中所有(多维)点集之间距离的平均值来量化组相似性。 我可以很容易地手动为每对组手动完成此操作,如下所示: library(dplyr) library(tibble) library(
在 OpenXML 中用于指定大小或 X、Y 坐标的度量单位是什么? (介绍)。 将那些与像素匹配是否有意义,如果是这样,那些如何转换为像素? graphicFrame.Transform = new
我想知道是否有人可以帮助我替换过渡层中的值。 如果我尝试: transitionlayer[transitionlayer >= 0.14] = 0.14 : comparison (5) is
我在 firebase 中有一个列表,其中包括地理位置(经度和纬度),并且我想获得距给定坐标最近的 10 个位置。 我正在从 MySQL 过渡,在那里我将计算 SELECT 中的距离, 并在 ORDE
如何在 Python 中根据 2 个 GPS 坐标计算速度、距离和方向(度)?每个点都有纬度、经度和时间。 我在这篇文章中找到了半正矢距离计算: Calculate distance between
关闭。这个问题需要多问focused 。目前不接受答案。 想要改进此问题吗?更新问题,使其仅关注一个问题 editing this post . 已关闭 6 年前。 Improve this ques
我只想使用 matplotlib 标记两条曲线之间发生最大偏差的位置。请帮助我。 垂直距离适用于 Kolmogorov–Smirnov test import numpy as np %matplot
我有一个包含数万行重复项的文件。我想根据行号找到重复项之间的平均时间/距离。 例如:(其中第一列是行号) 1 string1 2 string2 3 string2 4 string1 5 strin
用公式speed=distance/time计算时间 但时间总是0我的输入是 distance=10 和 speed=5 我的输出必须 = 2 #include int main() { in
我正在使用 Levenshtein 算法来查找两个字符串之间的相似性。这是我正在制作的程序的一个非常重要的部分,因此它需要有效。问题是该算法没有发现以下示例相似: CONAIR AIRCON 算法给出
对于一个房地产网站,我需要实现一个允许搜索文本和距离的搜索机制。 当 lat 和 lon 记录在单独的列中时,在 MySQL 表上进行距离计算很容易,但房子往往有 LOT true/false 属性。
是否可以在触发前更改 UIPanGestureRecognizer 的距离?目前的实现似乎在触发前有 5-10 像素的距离余量,我想降低它如果可能的话。 原因是我将 UIPanGestureRecog
我试图找到两个网格之间的偏差。例如在 3d 空间中定义的两组点之间的差异,我计划使用一些 3d 可视化工具来可视化距离,例如QT3d 或一些基于开放式 gl 的库。 我有两组网格,基本上是两个 .ST
所以,我有这个函数可以快速返回两个字符串之间的 Levenshtein 距离: Function Levenshtein(ByVal string1 As String, ByVal string2
我正在尝试用字典创建一个光学字符识别系统。 事实上,我还没有实现字典=) 我听说有一些基于 Levenstein 距离的简单指标,这些指标考虑了不同符号之间的不同距离。例如。 'N' 和 'H' 彼此
我在PostGIS数据库(-4326)中使用经纬度/经度SRID。我想以一种有效的方式找到最接近给定点的点。我试图做一个 ORDER BY ST_Distance(point, ST_GeomF
我想从线串的一端开始提取沿线串已知距离处的点的坐标。 例如: library(sf) path % group_by(L1) %>% summarise(do_union =
我已经编写了这些用于聚类基于序列的数据的函数: library(TraMineR) library(cluster) clustering <- function(data){ data <- s
是否可以设置 UILabel 的行之间的距离,因为我有一个 UILabel 包含 3 行,并且换行模式是自动换行? 最佳答案 如果您指的是“前导”,它指的是类型行之间的间隙 - 您无法在 UILabe
我是一名优秀的程序员,十分优秀!