C++11(clang++ 3.9) 解法, 执行用时: 157ms, 内存消耗: 9320K, 提交时间: 2019-03-09 22:27:12

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#define N 1000005
#define ll long long
using namespace std;
const double eps=1e-12;
char buf[1<<20],*p1,*p2;
#define GC (p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?0:*p1++)
inline void _R(int &x)
{
	char t=GC;
	while(t<48||t>57)t=GC;
	for(x=0;t>47&&t<58;t=GC)x=(x<<3)+(x<<1)+t-48;
}
struct node{int x,y;}P[N],S[N];
node operator+(node a,node b){return (node){a.x+b.x,a.y+b.y};}
node operator-(node a,node b){return (node){a.x-b.x,a.y-b.y};}
ll operator*(node a,node b){return 1ll*a.x*b.y-1ll*a.y*b.x;}
bool operator<(node a,node b)
{
	if(a.x!=b.x)return a.x>b.x;
	return a.y<b.y;
}
int n,top;
inline double f(double x)
{
	double Max=-9e18,y=1/x;
	for(register int i=1;i<=top;i++)
	{
		double t=x*S[i].x+y*S[i].y+S[i].x+S[i].y;
		Max=Max<t?t:Max;
	}
	return Max;
}
double DC(double l,double r)
{
	double res;
	while(r-l>=eps)
	{
		double lmid=l+(r-l)/3,lans=f(lmid);
		double rmid=r-(r-l)/3,rans=f(rmid);
		if(lans>rans)l=lmid,res=rans;
		else r=rmid,res=lans;
	}
	return res;
}
int main()
{
	_R(n);
	for(register int i=1;i<=n;i++)_R(P[i].x),_R(P[i].y);
	sort(P+1,P+n+1);
	for(register int i=1;i<=n;i++)
	{
		while(top>1&&(P[i]-S[top-1])*(S[top]-S[top-1])>=0)top--;
		S[++top]=P[i];
	}
	printf("%.4lf",DC(eps,10));
}