记录编号	375906	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	大灾变	最终得分	100
用户昵称	New World	是否通过	通过
代码语言	C++	运行时间	5.008 s
提交时间	2017-02-26 10:17:22	内存使用	72.41 MiB

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define LL long long
#define Inf 2e100
#define eps 1e-12
const int maxn=1050000;
struct Point{
	double x,y;
	Point(double xx=0,double yy=0){x=xx;y=yy;}
	void input(){scanf("%lf%lf",&x,&y);}
	void output(){printf("<<%.3lf %.3lf>>",x,y);}
};
typedef Point Vector;

int dcmp(double x)
{return fabs(x)<eps ? 0 : x>0 ? 1 :-1;}

bool operator == (Vector A,double x)
{return dcmp(A.x-x)==0 && dcmp(A.y-x)==0;}

bool operator < (Point A,Point B)
{return A.x!=B.x ? A.x<B.x : A.y<B.y;}

Vector operator - (Point A,Point B)
{return Vector(A.x-B.x,A.y-B.y);}

Point operator + (Point A,Vector B)
{return Point(A.x+B.x,A.y+B.y);}

Vector operator * (Vector A,double x)
{return Vector(A.x*x,A.y*x);}

double Cross(Vector A,Vector B)
{return A.x*B.y-A.y*B.x;}

double Dot(Vector A,Vector B)
{return A.x*B.x+A.y*B.y;}

double Length(Vector A)
{return sqrt(Dot(A,A));}

struct Line{
	Point P;Vector v;
	double ang;
	Line(){};
	Line(Point A,Vector B){
		P=A;v=B;
		ang=atan2(v.y,v.x);
	}
	bool operator < (const Line & A)const{
		return ang<A.ang;
	}
};

bool OnLeft(Line L,Point P)
{return dcmp(Cross(L.v,P-L.P))>=0;}

Point LineInterSection(Line A,Line B){
	if(B.v==0 && A.v==0)return Point(Inf,Inf);
	if(B.v==0){
		if(dcmp(Cross(A.v,B.P-A.P))==0)return B.P;
	}
	if(A.v==0){
		if(dcmp(Cross(B.v,A.P-B.P))==0)return A.P;
	}
	Vector u=A.P-B.P;
	double t=Cross(B.v,u)/Cross(A.v,B.v);
	return A.P+A.v*t;
}

int HalfPlaneInterSection(Line *L,int n,Point *poly){
	sort(L,L+n);
	Point *p=new Point[n];
	Line *q=new Line[n];
	int head,tail;
	q[head=tail=0]=L[0];
	for(int i=1;i<n;i++){
		while(head<tail && !OnLeft(L[i],p[tail-1]))tail--;
		while(head<tail && !OnLeft(L[i],p[head  ]))head++;
		q[++tail]=L[i];
		if(dcmp(Cross(q[tail].v,q[tail-1].v))==0){
			tail--;
			if(OnLeft(q[tail],L[i].P))q[tail]=L[i];
		}
		p[tail-1]=LineInterSection(q[tail],q[tail-1]);
	}
	while(head<tail && !OnLeft(q[head],p[tail-1]))tail--;
	if(tail-head<=1)return 0;
	p[tail]=LineInterSection(q[tail],q[head]);
	int m=0;
	for(int i=head;i<=tail;i++)poly[++m]=p[i];
	return m;
}

int n,cnt;
Point p[maxn],poly[maxn];
Line L[maxn];
void Init();
int main(){
	freopen("cataclysm.in","r",stdin);
	freopen("cataclysm.out","w",stdout);
    Init();
    return 0;
}
void Init(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)p[i].input();
	sort(p+1,p+n+1);
	for(int i=1;i<n;i++)
		L[cnt++]=Line(p[i],p[i+1]-p[i]);
	L[cnt++]=Line(p[n],Vector(0,1));
	L[cnt++]=Line(p[1],Vector(0,-1));
	L[cnt++]=Line(Point(0,Inf),Vector(-1,0));
	int m=HalfPlaneInterSection(L,cnt,poly);
	Point flyer;flyer.y=Inf;
	for(int i=1;i<=m;i++)
		if(dcmp(poly[i].y-flyer.y)<0)
			flyer=poly[i];
	int i=1,j=1;m--;
	//for(int i=1;i<=m;i++)poly[i].output();
	Point Fire;double ans=Inf;
	//从山脉对应下凸壳
	while(p[i+1].x<poly[1].x)i++;
	for(;i<=n;i++){
		if(p[i].x>poly[m].x)break;
		while(poly[j+1].x<p[i].x)j++;
		Line l1=Line(p[i],Vector(0,1));
		Line l2=Line(poly[j],poly[j+1]-poly[j]);
		Point Inter=LineInterSection(l1,l2);
		//Inter.output();
		double len=Length(Inter-p[i]);
		if(dcmp(len-ans)==-1){
			Fire=Inter;ans=len;
		}
	}
	//从下凸壳对应山脉
	i=1;j=1;
	while(p[i+1].x<poly[1].x)i++;
	for(;j<=m;j++){
		if(p[i].x>poly[m].x)break;
		while(p[i+1].x<poly[j].x)i++;
		Line l1=Line(poly[j],Vector(0,-1));
		Line l2=Line(p[i],p[i+1]-p[i]);
		Point Inter=LineInterSection(l1,l2);
		double len=Length(Inter-poly[j]);
		if(dcmp(len-ans)==-1){
			Fire=poly[j];ans=len;
		}
	}
	printf("%.2lf %.2lf\n",Fire.x,Fire.y);
	printf("%.2lf %.2lf\n",flyer.x,flyer.y);
	//printf("%d\n",m);
}