自动搬运

查看原文

来自洛谷，原作者为

	Red_river Q.E.D. ■|去证明，去实现|如果你总是和别人一起做他们做的事，你又怎么能知道自己是谁呢？|人生天地之间，若白驹之过隙，忽然而已。

搬运于2025-08-24 22:25:59，当前版本为作者最后更新于2024-03-04 13:06:16，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目大意

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

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

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

时间复杂度分析：$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;}