P7027 [NWRRC2017] Intelligence in Perpendicularia 题解

· · 题解

题目大意

首先这道题，就是变相的给你一个图形，然后让你求“安全”的边是有多长。（一个单位长度的边是安全的当且仅当它向外平移后能与其余边相遇）。

“安全”的定义可以转化成：不被算在最外层的边的线，就是“安全”的线。

所以我们就可以用总周长减去不“安全”的长就行了。

时间复杂度分析： O ( N ) 。

code

#include<bits/stdc++.h>
#define INF 1e6
#define M 1005
using namespace std;
int n,m,k,jk,x2,y2,ans,sum,x[M],y[M];//y1会编译错误 
int u=-INF,d=INF,l=INF,r=-INF;
void solve(int x,int y)
{
    u=max(u,y);r=max(r,x);
    d=min(d,y);l=min(l,x);
    sum+=abs(x-x2)+abs(y-y2);
    x2=x;y2=y;
}
int main()
{
    scanf("%d%d%d",&n,&x[1],&y[1]);x2=x[1],y2=y[1];
    for(register int i=2;i<=n;++i) scanf("%d%d",&x[i],&y[i]);
    //输入部分 为了后面统一处理： 
    for(register int i=2;i<=n;++i) solve(x[i],y[i]);//处理  
    sum+=abs(x[1]-x2)+abs(y[1]-y2);//首尾相连 
    printf("%d",sum-(r-l+u-d)*2);//输出 
    return 0;}