Cod sursa(job #1433561)

Utilizator livliviLivia Magureanu livlivi Data 9 mai 2015 16:02:48
Problema Rubarba Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.16 kb
#include<cstdio>
#include<algorithm>
#include<cmath>
#define N 100000
using namespace std;

struct punct{
    long long x,y;
};

struct dreapta{
    long long A,B,C;
};

struct arie{
    long long numi,numa;
};


punct v[N+1];
int n;
punct p;
arie minim,ar;

int stk[N+1];
int k;


long long mod(long long a){
    if (a<0) return -a;
    return a;
}


long long supr(int a,int b,int c){
    return mod((v[a].x-v[b].x)*(v[a].y+v[b].y)+(v[b].x-v[c].x)*(v[b].y+v[c].y)+(v[c].x-v[a].x)*(v[c].y+v[a].y));
}


long long dist(punct a,dreapta d){
    return d.A*a.x+d.B*a.y+d.C;
}


int next(int i){
    return i%n+1;
}


bool meow(punct a,punct b){
    long long pa,pb;
    pa=mod((a.y-p.y)*(b.x-p.x));
    pb=mod((b.y-p.y)*(a.x-p.x));

    if (a.x<=p.x &&b.x>p.x) return true;
    if (a.x>p.x &&b.x<=p.x) return false;
    if (a.x<=p.x &&b.x<=p.x){
        if (pa<pb) return true;
        if (pa==pb &&a.y>b.y) return true;
        return false;
    }
    if (pa>pb) return true;
    if (pa==pb &&a.y>b.y) return true;
    return false;
}


void infasuratoare(){
    int i;

    sort(v+2,v+n+1,meow);

    stk[1]=2;
    stk[2]=3;
    k=3;

    for(i=4;i<=n;i++){
        while(supr(1,stk[k-2],i)==supr(1,stk[k-2],stk[k-1])+supr(1,stk[k-1],i)+supr(stk[k-1],stk[k-2],i) &&k>2) k--;
        stk[k]=i;
        k++;
    }

    if (mod((v[stk[k-1]].y-v[1].y)*(v[stk[k-2]].x-v[1].x))==mod((v[stk[k-2]].y-v[1].y)*(v[stk[k-1]].x-v[1].x)))
        k--;

    for(i=1;i<k;i++)
        v[i+1]=v[stk[i]];

    n=k;
}


void rezolva(){
    int i,up,left,right,j;
    long long aux;
    dreapta d;

    d.A=v[1].y-v[2].y;
    d.B=v[2].x-v[1].x;
    d.C=v[1].x*v[2].y-v[1].y*v[2].x;

    up=1;
    for(i=2;i<=n;i++){
        if (mod(dist(v[i],d))>mod(dist(v[up],d))) up=i;
    }

    minim.numa=mod(dist(v[up],d));
    minim.numi=d.A*d.A+d.B*d.B;

    d.C=d.B;
    d.B=d.A;
    d.A=-d.C;
    d.C=0;

    left=1;
    right=1;
    for(i=2;i<=n;i++){
        aux=dist(v[i],d);

        if (aux<dist(v[left],d)) left=i;
        if (aux>dist(v[right],d)) right=i;
    }

    minim.numa=minim.numa*mod(dist(v[left],d)-dist(v[right],d));

    for(i=2;i<=n;i++){
        j=next(i);
        d.A=v[i].y-v[j].y;
        d.B=v[j].x-v[i].x;
        d.C=v[i].x*v[j].y-v[i].y*v[j].x;

        while(mod(dist(v[next(up)],d))>mod(dist(v[up],d))) up=next(up);

        ar.numa=mod(dist(v[up],d));
        ar.numi=d.A*d.A+d.B*d.B;

        d.C=d.B;
        d.B=d.A;
        d.A=-d.C;
        d.C=0;

        if (dist(v[left],d)>dist(v[right],d)){
            j=left;
            left=right;
            right=j;
        }

        while(dist(v[next(right)],d)>dist(v[right],d)) right=next(right);

        while(dist(v[next(left)],d)<dist(v[left],d)) left=next(left);

        ar.numa=ar.numa*mod(dist(v[left],d)-dist(v[right],d));

        if (minim.numa*ar.numi>ar.numa*minim.numi) minim=ar;
    }
}



int main(){
    freopen ("rubarba.in","r",stdin);
    freopen ("rubarba.out","w",stdout);
    int i,j=1;

    scanf ("%d",&n);
    for(i=1;i<=n;i++){
        scanf ("%lld%lld",&v[i].x,&v[i].y);

        if (v[i].y<v[j].y) j=i;
    }

    p=v[j];
    v[j]=v[1];
    v[1]=p;

    infasuratoare();

    rezolva();

    printf ("%.2lf",1.0*minim.numa/minim.numi);
    return 0;
}