记录编号	367125	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	大灾变	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	1.927 s
提交时间	2017-01-28 16:35:15	内存使用	46.07 MiB

#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
typedef double db;
const int N=1e6+10;
const db eps=1e-6;
int n,tail;
struct pt{
	db x,y;
	pt operator + (const pt &a)const{return (pt){x+a.x,y+a.y};}
	pt operator - (const pt &a)const{return (pt){x-a.x,y-a.y};}
	db operator ^ (const pt &a)const{return x*a.y-y*a.x;}
	bool operator < (const pt &a)const{return x==a.x?y>a.y:x<a.x;}
}p[N],a[N],q[N],ans1,ans2;
db check(pt &x,pt &y,pt &z){//x到y到z转角是顺时针还是逆时针 
	return (y-x)^(z-x);
}
pt getline(pt x,pt y){//返回斜截式 
	db k=(x.y-y.y)/(x.x-y.x);
	return (pt){k,x.y-k*x.x};
}
pt point(pt &x,pt &y){//返回交点坐标 
	db k=-(x.y-y.y)/(x.x-y.x);
	return (pt){k,x.y+k*x.x};
}
int main()
{
	freopen("cataclysm.in","r",stdin);
	freopen("cataclysm.out","w",stdout);
	scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%lf%lf",&p[i].x,&p[i].y);
	sort(p+1,p+n+1);
	for (int i=1;i<n;i++) a[i]=getline(p[i],p[i+1]);
	a[0].x=-1e30;
	a[n]=getline(p[1],p[1]+(pt){-eps,1e6});//相当于垂直于x轴的直线，防止越界 
	a[n+1]=getline(p[n],p[n]+(pt){eps,1e6});
	sort(a,a+n+2);
	//构造半平面交的凸包 
	for (int i=1;i<=n+1;i++)
	if (abs(a[i].x-a[i-1].x)>eps){//筛掉斜率一样的直线 
		for (;1<tail&&check(q[tail-1],q[tail],a[i])>=0;tail--);
		q[++tail]=a[i];
	}
	db now=ans1.y=ans2.y=1e30;
	for (int i=1,j=1;i<tail;i++){
		pt tmp=point(q[i],q[i+1]);
		if (ans2.y>eps&&tmp.y<ans2.y) ans2=tmp;
		for (;j<=n&&p[j].x<=tmp.x;j++){
			if (now>eps&&p[j].x*q[i].x+q[i].y-p[j].y<now)
				now=p[j].x*q[i].x+q[i].y-p[j].y,ans1=(pt){p[j].x,now+p[j].y};
		}
		if (j<=n&&j>1){
			pt tmp2=getline(p[j-1],p[j]);
			if (now>eps&&tmp.y-(tmp.x*tmp2.x+tmp2.y)<now)
				now=tmp.y-(tmp.x*tmp2.x+tmp2.y),ans1=tmp;
		}
	}
	if (abs(ans1.x)<=eps) ans1.x=0;
	if (abs(ans1.y)<=eps) ans1.y=0;
	if (abs(ans2.x)<=eps) ans2.x=0;
	if (abs(ans2.y)<=eps) ans2.y=0;
	printf("%.2lf %.2lf\n",ans1.x,ans1.y);
	printf("%.2lf %.2lf\n",ans2.x,ans2.y);
	return 0;
}