欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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,不符合题意)。则对于任意一个题目输入的点,它的可行域(即对于此点符合条件的点的集合)如下:

UVA-1468 Restaurant(计算几何)
A/B如题意 C为任意题目给定点

则整个题目给定点的可行域为所有单个点可行域的交集,则大致如下图:

UVA-1468 Restaurant(计算几何)
我只画了AB上半部分,AB下半部分与上半部分为镜像对称

所以确定每个点的位置后,从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;
}

 

相关标签: 计算几何