CF50C Happy Farm 5 题解

· · 题解

题目

解析

看到这题就想到了二维凸包。

什么是凸包？

用不严谨的话来讲，给定二维平面上的点集，凸包就是将最外层的点连接起来构成的凸多边形，它能包含点集中所有的点。

比如，

点 (p_0,p_1,p_3,p_{10},p_{12}) 就是凸包的点集。

那这题和凸包有什么关系呢？

题意大概是这样的：用一条线围出一个区间，使其包含平面内的给定点，但点不能在线上。线可以出现在正方形网格的边和对角线上。

这似乎和凸包的定义非常像。考虑我们已经选出了这个凸包的点集，用满足条件的线将这些点一连，所有的点就全部包含在内了。

如果把这个点集往里收，就会导致有点被忽略的情况，就不满足要求了。

这个时候就需要考虑怎么算凸包上相邻两点的距离了。

考虑线是可以沿对角线走的，这样一定是最快的，然后走直线补齐差价就可以了。假设两点为 (x_1,y_1) 和 (x_2,y_2)，那么两点间的路程为 max\{|x_1-x_2|,|y_1-y_2|\}。

那么如何算凸包呢？

Graham 扫描法：

  1. 找出 坐标最小的点，若有多个，找出 坐标最小的点。
  2. 将其作为原点进行极角排序。
  3. 将这个点和排序所得的第一个点放入栈，然后用单调栈维护斜率单调点，扫描一遍，最后在单调栈里的点即为所求。

回到这道题目，由于不能过这个点，我们就考虑过离他们最近的点，即上下左右四个点。如果要过右上的点，那么把右边的点和上面的点相连，所用的长度比先前的一定短且符合题意。

这样我们就可以建出原来的点周围的四个点，以这些点为点求凸包，这个凸包一定是满足要求的。

用 Graham 求凸包需要注意一点，要去重点，不然会超时。

接下来我知道你们想要看什么。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<map>
using std::cin;using std::cout;
constexpr int N=100005,K=1e7;
int n,x,y,cnt,now;
double Ans;
struct Point{
    double x,y;
    Point(double X=0,double Y=0){
        x=X,y=Y;
    }
}p[N<<2],ans[N<<2];
std::map<int,std::map<int,bool> >q;
typedef Point Vector;
inline Vector operator -(Point a,Point b){
    return Vector(a.x-b.x,a.y-b.y);
}
inline double Cross(Vector a,Vector b){//叉积
    return a.x*b.y-a.y*b.x;
}
inline double dis(Point a,Point b){
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
inline bool cmp(Point a,Point b){
    double check=Cross(a-p[1],b-p[1]);
    return (check>0||check==0&&dis(p[0],a)<=dis(p[0],b));
}
inline double Dis(Point a,Point b){
    return std::max(std::fabs(a.x-b.x),std::fabs(a.y-b.y));
}
signed main(){
//  freopen("T1.in","r",stdin);
//  freopen("T1.out","w",stdout);
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    cin>>n;
    for(int i=1;i<=n;++i){
        cin>>x>>y;//x+=K;y+=K;
        if(!q[x][y]){
            p[++cnt]=(Point){x+1,y};
            p[++cnt]=(Point){x-1,y};
            p[++cnt]=(Point){x,y+1};
            p[++cnt]=(Point){x,y-1};
        }
        q[x][y]=1;//去重点。
    }
    for(int i=2;i<=cnt;++i)
        if(p[i].y<p[1].y||p[i].y==p[1].y&&p[i].x<p[1].x) std::swap(p[1],p[i]);
    std::sort(p+2,p+cnt+1,cmp);//按极角排序
    // cout<<'\n';
    // for(int i=1;i<=cnt;++i) cout<<p[i].x<<' '<<p[i].y<<'\n';
    ans[++now]=p[1];//求凸包
    for(int i=2;i<=cnt;++i){
        while(now>=2&&Cross(ans[now]-ans[now-1],p[i]-ans[now])<=0) --now;
        ans[++now]=p[i];
    }
    ans[now+1]=p[1];//cout<<'\n';
    for(int i=1;i<=now;++i) Ans+=Dis(ans[i],ans[i+1]);//,cout<<ans[i].x<<' '<<ans[i].y<<'\n';
    //计算长度
    cout<<(int)Ans;
    return 0;
}