记录编号	143972	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2011]Construct	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.179 s
提交时间	2014-12-19 11:59:25	内存使用	11.00 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
typedef long long LL;
const int SIZEN=200010;
const LL INF=1e10;
class Point{
public:
	LL x,y;
};
void print(Point p){printf("(%lld %lld)",p.x,p.y);}
Point operator - (Point a,Point b){return (Point){a.x-b.x,a.y-b.y};}
LL cross(Point a,Point b){return a.x*b.y-b.x*a.y;}
void calc(Point p[],int n,vector<Point> &H){//求上凸包,1和n必在凸包上,逆时针
	static LL Ys[SIZEN];
	for(int i=1;i<=n;i++) Ys[i]=p[i].y;
	sort(Ys+1,Ys+1+n);
	int tot=0;
	for(int i=1;i<=n;i++) if(i==1||Ys[i]!=Ys[i-1]) Ys[++tot]=Ys[i];
	static LL mn[SIZEN],mx[SIZEN];
	for(int i=1;i<=tot;i++) mn[i]=INF,mx[i]=-INF;
	for(int i=1;i<=n;i++){
		int ny=lower_bound(Ys+1,Ys+1+tot,p[i].y)-Ys;
		mn[ny]=min(mn[ny],p[i].x);
		mx[ny]=max(mx[ny],p[i].x);
	}
	for(int i=tot-1;i>=1;i--){
		mn[i]=min(mn[i],mn[i+1]);
		mx[i]=max(mx[i],mx[i+1]);
	}
	int start=lower_bound(Ys+1,Ys+1+tot,p[1].y)-Ys,end=lower_bound(Ys+1,Ys+1+tot,p[n].y)-Ys;
	for(int i=start;i<=tot;i++){
		H.push_back((Point){mx[i],Ys[i]});
		if(i<tot) H.push_back((Point){mx[i+1],Ys[i]});
	}
	for(int i=tot;i>=end;i--){
		H.push_back((Point){mn[i],Ys[i]});
		if(i>end) H.push_back((Point){mn[i],Ys[i-1]});
	}
}
Point P[SIZEN];
int N;
Point tp[SIZEN];
vector<Point> H1,H2;
LL calc_area(vector<Point> &H){
	LL ans=0;
	H.push_back(H[0]);
	for(int i=0;i<H.size()-1;i++)
		ans+=cross(H[i],H[i+1]);
	return ans/2;
}
void work(void){
	int L=1,R=1,U=1,D=1,tot;
	for(int i=2;i<=N;i++){
		if(P[i].x<=P[L].x) L=i;
		if(P[i].x>P[R].x) R=i;
		//这是为了在极限状态下把L和R错开
		if(P[i].y<P[D].y) D=i;
		if(P[i].y>P[U].y) U=i;
	}
	tot=0;for(int i=R;i<=(L<R?N+L:L);i++) tp[++tot]=(Point){P[i].x,P[i].y};
	calc(tp,tot,H1);
	tot=0;for(int i=(R<L?N+R:R);i>=L;i--) tp[++tot]=(Point){P[i].x,-P[i].y};
	calc(tp,tot,H2);
	for(int i=H2.size()-1;i>=0;i--)
		H1.push_back((Point){H2[i].x,-H2[i].y});
	LL len=2*(P[R].x-P[L].x+P[U].y-P[D].y);
	printf("%lld\n%lld\n",len,calc_area(H1));
}
void read(void){
	scanf("%d",&N);
	for(int i=1;i<=N;i++){
		scanf("%lld%lld",&P[i].x,&P[i].y);
		P[N+i]=P[i];
	}
}
int main(){
	freopen("construct.in","r",stdin);
	freopen("construct.out","w",stdout);
	read();
	work();
	return 0;
}