UVA-1468 Restaurant(计算几何)
程序员文章站
2022-06-04 08:20:39
...
题目链接:https://vjudge.net/problem/UVA-1468
题目大意:给你n个点和一个m×m的坐标纸(坐标范围0-m-1),n个点中前两个为A和B,要求给出坐标纸上满足以下性质的点的数目——某一个点满足条件当且仅当对任意一个给定点C,它对A曼哈顿距离小于C对A曼哈顿距离 或 它对B曼哈顿距离小于C对B曼哈顿距离。
思路:显然符合条件的点都在AB之间(因为如果在AB两侧则假设此点在A左侧,则此点到A距离小于A,到B距离也小于B,不符合题意)。则对于任意一个题目输入的点,它的可行域(即对于此点符合条件的点的集合)如下:
则整个题目给定点的可行域为所有单个点可行域的交集,则大致如下图:
所以确定每个点的位置后,从A到B扫一遍确定每个点右侧的值,在从B到A扫一遍确定每个点左侧的值即可,最后答案即为AB之间每一个x的高度的和(不能超出上下边界)。
下面是AC代码:
#include<bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f;
const int MAXN=6e4+5;
int h[MAXN];
int main()
{
#ifdef ZYP
freopen("uva-1468.01.inp","r",stdin);
#endif
int t;
scanf("%d",&t);
while(t--)
{
int m,n;
memset(h,0x3f,sizeof(h));
scanf("%d%d",&m,&n);
pair<int,int>a,b;
scanf("%d%d",&a.first,&a.second);
scanf("%d%d",&b.first,&b.second);
for(int i=0;i<n-2;i++)
{
int x,y;
scanf("%d%d",&x,&y);
if(x<a.first||x>b.first)continue;
h[x]=min(h[x],abs(y-b.second)-1);
}
h[a.first]=-1;
for(int i=a.first+1;i<b.first;i++)h[i]=min(h[i],h[i-1]+1);
h[b.first]=-1;
for(int i=b.first-1;i>a.first;i--)h[i]=min(h[i],h[i+1]+1);
long long ans=0;
for(int i=a.first;i<=b.first;i++)
{
int tall=min(h[i]+a.second,m-1);
int low=max(-h[i]+a.second,0);
if(h[i]==-1)continue;
ans+=tall-low+1;
}
printf("%lld\n",ans);
}
return 0;
}
上一篇: MySQL触发器和游标
下一篇: The 2019 ACM-ICPC China Shannxi Provincial Programming Contest C.Angel's Journey
推荐阅读
-
几何画板怎么通过度量计算直线或曲线的方程?
-
BZOJ1278: 向量vector(计算几何 随机化乱搞)
-
云计算420亿美元规模 安防应用占据几何?
-
51nod 1298 圆与三角形——计算几何
-
计算几何与计算机图形学方面的一些资源及源代码 MatlabFortranC#C++C
-
计算几何与计算机图形学方面的一些资源及源代码 MatlabFortranC#C++C
-
点到线段的距离 计算几何
-
计算机图形与OpenGL学习七(三维几何变换1.三维平移与三维坐标轴旋转)
-
计算几何(空间几何 + 三分) - Dome of Circus - UVA 1473
-
计算机图形学(四)几何变换_5_三维空间的几何变换_1_三维平移