Cod sursa(job #2877273)

Utilizator livliviLivia Magureanu livlivi Data 24 martie 2022 14:50:55
Problema Rubarba Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.73 kb
#include<fstream>
#include<iomanip>
#include<cstdio>
#include<algorithm>
#include<cmath>
#define N 100000
#define M 1000000000
using namespace std;
 
struct punct{
    long long x,y;
};
 
struct dreapta{
    long long A,B,C;
};
 
struct arie{
    long long numi,numa;
 
    bool operator > (arie a){
        long long aux;
        int vnumi[2],vnuma[2],vanumi[2],vanuma[2],prod1[4],prod2[4];
 
        if (numi<=a.numi &&numa>=a.numa) return true;
        if (numi>=a.numi &&numa<=a.numa) return false;
 
        vnumi[0]=numi%M;
        vnumi[1]=numi/M;
        vnuma[0]=numa%M;
        vnuma[1]=numa/M;
        vanumi[0]=a.numi%M;
        vanumi[1]=a.numi/M;
        vanuma[0]=a.numa%M;
        vanuma[1]=a.numa/M;
 
        aux=(long long)vnuma[0]*vanumi[0];
        prod1[0]=aux%M;
        aux=aux/M+(long long)vnuma[0]*vanumi[1]+(long long)vnuma[1]*vanumi[0];
        prod1[1]=aux%M;
        aux=aux%M+(long long)vnuma[1]*vanumi[1];
        prod1[2]=aux%M;
        prod1[3]=aux/M;
 
        aux=(long long)vanuma[0]*vnumi[0];
        prod2[0]=aux%M;
        aux=aux/M+(long long)vanuma[0]*vnumi[1]+(long long)vanuma[1]*vnumi[0];
        prod2[1]=aux%M;
        aux=aux%M+(long long)vanuma[1]*vnumi[1];
        prod2[2]=aux%M;
        prod2[3]=aux/M;
 
        if (prod1[3]<prod2[3]) return false;
        if (prod1[3]>prod2[3]) return true;
        if (prod1[2]<prod2[2]) return false;
        if (prod1[2]>prod2[2]) return true;
        if (prod1[1]<prod2[1]) return false;
        if (prod1[1]>prod2[1]) return true;
        if (prod1[0]<prod2[0]) return false;
        if (prod1[0]>prod2[0]) return true;
        return false;
    }
};
 
 
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)){
            d.A = -d.A;
            d.B = -d.B;
        }
 
        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 ((long double)minim.numa/minim.numi>(long double)ar.numa/ar.numi) minim=ar;
    }
}
 
 
 
int main(){
    freopen ("rubarba.in","r",stdin);
    //freopen ("rubarba.out","w",stdout);
    ofstream fout("rubarba.out");
    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",(long double)minim.numa/minim.numi);
    fout<<fixed<<setprecision(2)<<(long double)minim.numa/minim.numi;
    return 0;
}