Cod sursa(job #1788415)

Utilizator alexpetrescuAlexandru Petrescu alexpetrescu Data 25 octombrie 2016 23:07:50
Problema Rubarba Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.27 kb
#include <cstdio>
#include <complex>
#include <cmath>
#include <utility>
#include <algorithm>

#define cpx std::complex <double>

#define myc std::pair <int, int>
#define x first
#define y second

#define MAXN 100000

cpx w1, w2;
myc v[MAXN+1];
int st[MAXN+2];

inline long long arie(int i, int j, int p){
    return 1LL*v[i].x*v[j].y-1LL*v[j].x*v[i].y+1LL*v[j].x*v[p].y-1LL*v[p].x*v[j].y+1LL*v[p].x*v[i].y-1LL*v[i].x*v[p].y;
}

inline cpx rotim(myc a, double ang){
    w1=cpx(a.x, a.y);
    w2=cpx(cos(ang), sin(ang));
    w1*=w2;
    return w1;
}

int main(){
    int vf, n, syx, sxi, sxx, aux;
    double ans, xmin, xmax, ymin, ymax, ang;
    cpx a, b;
    FILE *fin, *fout;
    fin=fopen("rubarba.in", "r");
    fout=fopen("rubarba.out", "w");
    fscanf(fin, "%d", &n);
    for(int i=1; i<=n; i++)
        fscanf(fin, "%d%d", &v[i].x, &v[i].y);
    std::sort(v+1, v+n+1);
    st[1]=1;
    vf=1;
    for(int i=2; i<n; i++){
        if(arie(1, n, i)>=0){
            while((vf>1)&&(arie(st[vf-1], st[vf], i)>0))
                vf--;
            st[++vf]=i;
        }
    }
    while((vf>1)&&(arie(st[vf-1], st[vf], n)>0))
        vf--;
    st[++vf]=n;
    for(int i=n-1; i>1; i--){
        if(arie(1, n, i)<0){
            while((vf>1)&&(arie(st[vf-1], st[vf], i)>0))
                vf--;
            st[++vf]=i;
        }
    }
    while((vf>1)&&(arie(st[vf-1], st[vf], 1)>0))
        vf--;
    st[++vf]=1;
    for(int i=1, j=vf; i<j; i++, j--){
        aux=st[i];
        st[i]=st[j];
        st[j]=aux;
    }
    ang=atan2(v[st[2]].y-v[st[1]].y, v[st[2]].x-v[st[1]].x);
    a=rotim(v[st[1]], -ang);
    ymin=ymax=a.imag();
    xmin=xmax=a.real();
    syx=sxi=sxx=1;
    for(int i=2; i<vf; i++){
        a=rotim(v[st[i]], -ang);
        if(a.imag()>ymax) ymax=a.imag(), syx=i;
        if(a.real()<xmin) xmin=a.real(), sxi=i;
        if(a.real()>xmax) xmax=a.real(), sxx=i;
    }
    ans=(xmax-xmin)*(ymax-ymin);
    for(int i=2; i<vf; i++){
        ang=atan2(v[st[i+1]].y-v[st[i]].y, v[st[i+1]].x-v[st[i]].x);
        a=rotim(v[st[i]], -ang);
        ymin=a.imag();
        a=rotim(v[st[syx]], -ang);
        ymax=a.imag();
        aux=syx+1;
        if(aux>=vf) aux-=vf-1;
        b=rotim(v[st[aux]], -ang);
        while(b.imag()>ymax){
            ymax=b.imag();
            syx=aux;
            aux++;
            if(aux>=vf) aux-=vf-1;
            b=rotim(v[st[aux]], -ang);
        }
        a=rotim(v[st[sxi]], -ang);
        xmin=a.real();
        aux=sxi+1;
        if(aux>=vf) aux-=vf-1;
        b=rotim(v[st[aux]], -ang);
        while(b.real()<xmin){
            xmin=b.real();
            sxi=aux;
            aux++;
            if(aux>=vf) aux-=vf-1;
            b=rotim(v[st[aux]], -ang);
        }
        a=rotim(v[st[sxx]], -ang);
        xmax=a.real();
        aux=sxx+1;
        if(aux>=vf) aux-=vf-1;
        b=rotim(v[st[aux]], -ang);
        while(b.real()>xmax){
            xmax=b.real();
            sxx=aux;
            aux++;
            if(aux>=vf) aux-=vf-1;
            b=rotim(v[st[aux]], -ang);
        }
        if((xmax-xmin)*(ymax-ymin)<ans)
            ans=(xmax-xmin)*(ymax-ymin);
    }
    fprintf(fout, "%.2lf\n", ans);
    fclose(fin);
    fclose(fout);
    return 0;
}