[ZJ] b221: 6. 耕者有其田

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
using namespace std;
struct P{
    double x,y;
}s[105],p[105],h[105];
int n,m=0;
double cross(P a,P b,P c){
    P A,B;
    A=(P){b.x-a.x,b.y-a.y};
    B=(P){c.x-a.x,c.y-a.y};
    return A.x*B.y-A.y*B.x;
}
int cmp(P a,P b){
    if(a.x!=b.x) return a.x<b.x;
    return a.y<b.y;
}
void convex(){
    int i,t;
    for(i=0;i<n;i++){
        while(m>=2 && cross(p[m-2],p[m-1],s[i])<=0) m--;
        p[m++]=s[i];
    }
    for(i=n-2,t=m+1;i>=0;i--){
        while(m>=t && cross(p[m-2],p[m-1],s[i])<=0) m--;
        p[m++]=s[i];
    }
}
double calc(P r[],int L){
    double ans=0;
    int i;
    for(i=0;i<L-1;i++)
        ans+=r[i].x*r[i+1].y-r[i].y*r[i+1].x;
    return ans/2;
}
int main(){
    int i,j,st,add;
    double all,tmp,l=0xffffffff,r=0,mi,X,Y;
    scanf("%d",&n);
    for(i=0;i<n;i++){
        scanf("%lf%lf",&s[i].x,&s[i].y);
        mi=s[i].y/s[i].x;
        if(mi<l) l=mi;
        if(mi>r) r=mi;
    }

    sort(s,s+n,cmp);
    convex();
    all=calc(p,m);
    while(r-l>1e-6){
        mi=(l+r)/2;
        st=0,add=0;
        P pp[2];
        for(i=0;i<m;i++){
            if(add==1) h[st++]=p[i];
            if((mi*p[i].x-p[i].y)*(mi*p[i+1].x-p[i+1].y)<=0){
                X=(p[i].x*p[i+1].y-p[i].y*p[i+1].x)/(mi*p[i].x-p[i].y-mi*p[i+1].x+p[i+1].y);
                Y=mi*X;
                if(add<2){
                    if(add==1 && X==pp[0].x && Y==pp[0].y) continue;
                    pp[add]=(P){X,Y};
                    h[st++]=pp[add++];
                }
            }
        }
        h[st++]=pp[0];
        tmp=calc(h,st);
        if(fabs(tmp*2-all)<1e-6) break;
        if(h[1].x*mi-h[1].y<0){
            if(tmp*2<all) r=mi;
            else l=mi;
        }
        else{
            if(tmp*2<all) l=mi;
            else r=mi;
        }
    }
    printf("%.4lf\n",mi);
}