记录编号	376261	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	大灾变	最终得分	100
用户昵称	_Itachi	是否通过	通过
代码语言	C++	运行时间	2.767 s
提交时间	2017-02-26 21:27:39	内存使用	122.36 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn=1000015;
const double EPS=1e-10,INF=1e30;
bool Cmp(double x){return x<0?x>-EPS:x<EPS;}
int Dcmp(double x){return Cmp(x)?0:(x<0?-1:1);}
struct Vec {
	#define Poi Vec
	double x,y;
	void read(){scanf("%lf%lf",&x,&y);}
	void out(){printf("%.2f %.2f\n",x,y);}
	bool operator < (const Poi &a)const{
		return Cmp(x-a.x)?y<a.y:x<a.x;
	}
	Vec operator - (const Vec &a)const{
		return (Vec){x-a.x,y-a.y};
	}
	double operator * (const Vec &a)const{
		return x*a.y-y*a.x;
	}
	Poi operator + (const Vec &a)const{
		return (Poi){x+a.x,y+a.y};
	}
	Vec operator ^ (const double &a)const{
		return (Vec){x*a,y*a};
	}
}p[maxn],H[maxn],st[maxn];
struct Line {
	Poi p;Vec v;double ang;
	void init(Poi P,Vec V){p=P,v=V,ang=atan2(v.y,v.x);}
	void qinit(Poi P,Vec V){p=P,v=V;}
	double H(double x){
		return (p+(v^((x-p.x)/v.x))).y;
	}
	bool operator < (const Line &a)const{
		return Cmp(ang-a.ang)?v.y<a.v.y:ang<a.ang;
	}
	Poi operator * (const Line &a)const{
		Vec u=p-a.p;
		double t=(a.v*u)/(v*a.v);
		return p+(v^t);
	}
	bool left(Poi a)const{
		return Dcmp(v*(a-p))>0;
	}
}q[maxn],L[maxn];
int HalfPlane(int n){
	int s,t,i;sort(L,L+n);
	q[s=t=0]=L[0];
	for(i=1;i<n;i++){
		while(s<t&&!L[i].left(p[t-1]))t--;
		while(s<t&&!L[i].left(p[s]))s++;
		q[++t]=L[i];
		if(Cmp(q[t].v*q[t-1].v)){
			t--;if(q[t].left(L[i].p))q[t]=L[i];
		}
		if(s<t)p[t-1]=q[t]*q[t-1];
	}
	while(s<t&&!q[s].left(p[t-1]))t--;
	if(t-s<=1)return 0;p[t]=q[s]*q[t];
	int m=0;
	for(i=s;i<=t;i++)st[m++]=p[i];
	return m;
}
void Rabit_ans(int n,int m){
	sort(st,st+m);
	int i,j=0,cot=0;
	for(i=0;i<m;i++)if(st[i].y+EPS<INF)p[cot++]=st[i];
	m=cot;
	for(i=0;i<m;i++)st[i]=p[i];
	Poi A1=st[0],A2=st[0];Line R;
	H[n]=H[n-1],H[n].x+=233;
	double ans1=st[0].y-H[0].y,ans2=st[0].y,tmp;
	for(i=1;i<m;i++){
		if(st[i].y<ans2)A2=st[i],ans2=st[i].y;
		if(Cmp(st[i].x-st[i-1].x))continue;
		R.qinit(st[i-1],st[i]-st[i-1]);
		while(j<n&&Dcmp(H[j].x-st[i].x)<=0){
			tmp=R.H(H[j].x);
			if(tmp-H[j].y+EPS<ans1)ans1=tmp-H[j].y,A1.x=H[j].x,A1.y=tmp;
			j++;
		}
		R.qinit(H[j-1],H[j]-H[j-1]);tmp=R.H(st[i].x);
		if(st[i].y-tmp+EPS<ans1)ans1=st[i].y-tmp,A1.x=st[i].x,A1.y=st[i].y;
	}
	A1.out(),A2.out();
}
int main(){
	freopen("cataclysm.in","r",stdin);freopen("cataclysm.out","w",stdout);
	int n,i;scanf("%d",&n);
	for(i=0;i<n;i++)H[i].read();sort(H,H+n);
	L[0].init((Poi){0,INF},(Vec){-1,0});
	for(i=1;i<n;i++)L[i].init(H[i-1],H[i]-H[i-1]);
	L[n].init((Poi){H[n-1].x,0},(Vec){0,1}),n++,
	L[n++].init((Poi){H[0].x,0},(Vec){0,-1});
	Rabit_ans(n-2,HalfPlane(n));
}