[杂题] pku3269 曼哈顿距离的性质 at GCCFeli.cn

[杂题] pku3269 曼哈顿距离的性质

评论35次阅读2008.01.20 11:22; 作者：Felicia　

题目意思是给出平面上n个不相邻的点，要求到这n个点的曼哈顿距离之和最小的点的个数ans2，和这个最小距离ans1。
点的坐标范围是-10000到10000（这个很重要）

考虑到曼哈顿距离的定义：|x – x0| + |y – y0|
这个定义是线性的，对称的
因此考虑分别在两个方向上解这个问题（曼哈顿距离的性质）

对于x方向，定义x曼哈顿距离是|x – x0|，因为坐标范围很小，所以可以对所有可能的坐标，做一个线性扫描，求出fx，fx[x0]表示所有点到x0这个x坐标的x曼哈顿距离之和。对y方向相应地求出fy。
有了fx和fy，我们可以用O(1)时间算出所有点到某一坐标(x0, y0)的曼哈顿距离之和ans1。现在选出fx[x0] + fy[y0]的最小值（剔除那些输入的点），这一步我是把fx和fy分别排序做的，复杂度O(nlogn)。应该能利用点的不相邻性质做得更好。
现在统计满足题意的点的个数。利用fx计算数组nx，nx[i].coor表示此点的x坐标，nx[i].num表示x坐标是nx[i].coor的点的个数，nx[i].dist表示所有点到nx[i].coor的x曼哈顿距离之和。相应地计算ny。计算数组dd，dd[i]表示所有点到第i个点的曼哈顿距离之和。令t1 = sum(nx[i].num * ny[i].num), if (nx[i].dist + ny[i].dist == ans1)。令t2 = (dd[i] == ans1) 的个数。因此ans2 = t1 – t2。

下面是我的代码：

下载: pku3269.cpp

/**********************************************************************
Author: WHU_GCC
Created Time: 2008-1-19 20:26:13
File Name: pku3269.cpp
Description:
**********************************************************************/
#include <iostream>
#include <set>
using namespace std;

#define out(x) (cout << #x << ": " << x << endl)
typedef long long int64;
const int maxint = 0x7FFFFFFF;
const int64 maxint64 = 0x7FFFFFFFFFFFFFFFLL;
template <class T> void show(T a, int n) { for (int i = 0; i < n; ++i) cout << a[i] << ' '; cout << endl; }
template <class T> void show(T a, int r, int l) { for (int i = 0; i < r; ++i) show(a[i], l); cout << endl; }

const int maxn = 10010;

struct node_t
{
   int dist;
   int coor;
};

struct num_t
{
   int dist;
   int num;
};

bool operator <(const node_t &a, const node_t &b)
{
   return a.dist < b.dist;
}

int n;
int x[maxn];
int y[maxn];
node_t fx[maxn * 2];
node_t fy[maxn * 2];
int hx[maxn * 2];
int hy[maxn * 2];
int minx, miny, maxx, maxy;
int dd[maxn];

set <pair<int, int> > ptrset;

num_t nx[maxn];
num_t ny[maxn];
int lnx, lny;

int main()
{
   scanf("%d", &n);
   memset(hx, 0, sizeof(hx));
   memset(hy, 0, sizeof(hy));

   minx = miny = maxint;
   maxx = maxy = 0;
   ptrset.clear();
   for (int i = 0; i < n; i++)
   {
   scanf("%d%d", &x[i], &y[i]);
   x[i] += 10000;
   y[i] += 10000;
   ptrset.insert(make_pair(x[i], y[i]));
   hx[x[i]]++;
   hy[y[i]]++;
   minx <?= x[i];
   miny <?= y[i];
   maxx >?= x[i];
   maxy >?= y[i];
   }
   fx[minx].dist = 0;
   fx[minx].coor = minx;
   for (int i = minx + 1; i <= maxx; i++)
   fx[minx].dist += abs(i - minx) * hx[i];
   int numrx = n - hx[minx];
   int nummx = hx[minx];
   int numlx = 0;
   for (int i = minx + 1; i <= maxx; i++)
   {
   fx[i].dist = fx[i - 1].dist + numlx + nummx - numrx;
   fx[i].coor = i;
   numlx += nummx;
   nummx = hx[i];
   numrx -= nummx;
   }
   fy[miny].dist = 0;
   fy[miny].coor = miny;
   for (int i = miny + 1; i <= maxy; i++)
   fy[miny].dist += abs(i - miny) * hy[i];
   int numry = n - hy[miny];
   int nummy = hy[miny];
   int numly = 0;
   for (int i = miny + 1; i <= maxy; i++)
   {
   fy[i].dist = fy[i - 1].dist + numly + nummy - numry;
   fy[i].coor = i;
   numly += nummy;
   nummy = hy[i];
   numry -= nummy;
   }
   for (int i = 0; i < n; i++)
   dd[i] = fx[x[i]].dist + fy[y[i]].dist;

   sort(fx + minx, fx + maxx + 1);
   sort(fy + miny, fy + maxy + 1);
   int ans1;
   for (int i = minx; i <= maxx; i++)
   for (int j = miny; j <= maxy; j++)
   {
   if (ptrset.count(make_pair(fx[i].coor, fy[j].coor)) == 0)
   {
   ans1 = fx[i].dist + fy[j].dist;
   goto end;
   }
   }
   end:;
   lnx = 0;
   for (int i = minx; i <= maxx; i++)
   {
   if (i == minx)
   {
   nx[lnx].dist = fx[i].dist;
   nx[lnx].num = 1;
   lnx++;
   }
   else
   {
   if (fx[i].dist == nx[lnx - 1].dist)
   nx[lnx - 1].num++;
   else
   {
   nx[lnx].dist = fx[i].dist;
   nx[lnx].num = 1;
   lnx++;
   }
   }
   }

   lny = 0;
   for (int i = miny; i <= maxy; i++)
   {
   if (i == miny)
   {
   ny[lny].dist = fy[i].dist;
   ny[lny].num = 1;
   lny++;
   }
   else
   {
   if (fy[i].dist == ny[lny - 1].dist)
   ny[lny - 1].num++;
   else
   {
   ny[lny].dist = fy[i].dist;
   ny[lny].num = 1;
   lny++;
   }
   }
   }
   int ans2 = 0;
   for (int i = 0; i < lnx; i++)
   if (nx[i].dist <= ans1)
   {
   for (int j = 0; j < lny; j++)
   if (nx[i].dist + ny[j].dist <= ans1)
   {
   if (nx[i].dist + ny[j].dist == ans1)
   ans2 += nx[i].num * ny[j].num;
   }
   else break;
   }
   else break;
   for (int i = 0; i < n; i++)
   if (dd[i] == ans1)
   ans2--;
   printf("%d %d\n", ans1, ans2);
   return 0;
}

标签云: 代码 | 日志分类: 杂题

如需转载烦请添加以下信息: 本文转自Felicia@GCCFeli.cn

评论 (0)
引用通告 (0)
发表评论引用通告

暂无评论.

暂无引用通告

发表回复