曼哈顿最小距离公制 [英] Minimal distance in 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  scanf（％d％d，& pointsA [i] .st，& pointsA [i ] .nd）; 
} 
 
 for（int i = 0; i  scanf（％d％d，& pointsB [i] & pointsB [i] .nd）; 
} 
 
 for（int i = 0; i  for（int j = 0; j  if（abs（pointsA [i] .st-pointsB [j] .st）+ abs（pointsA [i] .nd- pointsB [j] .nd） dist = abs [i] .st  -  pointsB [j] .st）+ abs（pointsA [i] .nd  -  pointsB [j] .nd）; 
} 
} 
 printf（％lld\\\
，dist）; 
} 
} 
} 
  

我的代码在O n ^ 2），但太慢了。我不知道它是否有用，但y在pointsA总是> 0和y在pointsB总是<我的代码比较实际距离到下一个，并选择最小。

例如：

输入：

  2 
 3 
 -2 2 
 1 3 
 3 1 
 0 -1 
 -1 -2 
 1 -2 
 1 
 1 1 
 -1 -1 
  

$ b b

输出：

  5 
 4 
   manhattan_dist  c>因此，它不适用于 unsigned long long ）：
  #include< cstdlib> 
 #include< cstdio> 
 #include< cassert> 
 #include< vector> 
 #include< limits> 
 #include< algorithm> 
 
 typedef std :: pair< int，int>点; 
 typedef std :: vector< std :: pair< int，int> >点列表; 
 
 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<秒; 
} 
} 
 
 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<第一; 
} 
} 
 
 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  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\\\
，dist）; 
} 
} 
  
我的机器上的基准测试（Linux + i7 2.70 GHz + gcc -Ofast -march = native）：
  $ make bench 
 time ./test1< data.txt> test1_res 
 
 real 0m7.846s 
用户0m7.820s 
 sys 0m0.000s 
 time ./test2< data.txt> test2_res 
 
 real 0m0.605s 
用户0m0.590s 
 sys 0m0.010s 
  
  test1 是您的变体， test2 是我的。
 
I am trying to find the minimal distance in the Manhattan metric (x,y). I am searching for information about this. But I haven't found anything.  
#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);
        }
    }
}
My code works in O(n^2) but is too slow. I do not know whether it will be useful but y in pointsA always be > 0 and y in pointsB always be < 0. My code compare actually distance to next and chose smallest. 

for example:

input:
2
3
-2 2
1 3
3 1
0 -1
-1 -2
1 -2
1
1 1
-1 -1
Output:
5
4

解决方案
My solution (note for simplicity I do not care about overflow in manhattan_dist and for that reason it does not work with 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);
    }
}
Benchmark on my machine (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 is your variant, and test2 is mine.

                        
这篇关于曼哈顿最小距离公制的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！