Cod sursa(job #1098435)

Utilizator DaNutZ2UuUUBB Bora Dan DaNutZ2UuU Data 4 februarie 2014 20:18:38
Problema Rubarba Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.94 kb
#include<iostream>
#include<fstream>
#include<algorithm>
#include<iomanip>
#include<math.h>
using namespace std;
  
#define NMAX 100001
#define INF (1LL<<60)
#define eps 0.0000001
  
struct punct {
    int x,y;
};
  
punct v[NMAX],a[NMAX];
  
long long cross_product(punct a, punct b, punct c)
{
    return 1LL*(b.x-a.x)*(c.y-a.y)-1LL*(b.y-a.y)*(c.x-a.x);
}
  
struct cmp {
    bool operator () (const punct &a, const punct &b) {
        return cross_product(v[1],a,b)>=0;
    }
};
  
int graham_scan(int n)
{
    int nr,i;
    for(i=2;i<=n;i++)
        if(v[i].y<v[1].y || (v[i].y==v[1].y && v[i].x<v[1].x))
            swap(v[1],v[i]);
    sort(v+2,v+n+1,cmp());
    a[1]=v[1];
    a[2]=v[2];
    nr=2;
    for(i=3;i<=n;i++) {
        while(nr>=2 && cross_product(a[nr-1],a[nr],v[i])<=0)
            nr--;
        a[++nr]=v[i];
    }
    a[++nr]=a[1];
    return nr;
}
  
long double modul(long double x)
{
    if(x<=0)
        return -x;
    return x;
}
  
long double dist(double A, double B, double C, punct x)
{
    return (long double)(modul(0LL+1LL*A*x.x+1LL*B*x.y+C))/sqrtl(0LL+1LL*A*A+1LL*B*B);
}
  
double dist2(punct x, punct y)
{
    return (double)sqrtl(1LL*(x.x-y.x)*(x.x-y.x)+1LL*(x.y-y.y)*(x.y-y.y));
}
  
int egal(double x, double y)
{
    if(modul(x-y)<=eps)
        return 1;
    return 0;
}
  
int main ()
{
    int n,i,nr,j;
    double d1,d2,d3,sol,A,B,C,AA,C1,C2;
    ifstream f("rubarba.in");
    ofstream g("rubarba.out");
    f>>n;
    for(i=1;i<=n;i++)
        f>>v[i].x>>v[i].y;
    f.close();
    nr=graham_scan(n);
    sol=INF;
    for(i=1;i<=nr;i++) {
        v[i]=a[i];
    }
    n=nr;
    for(i=1;i<=nr-1;i++) {
        d1=0;
        d2=0;
        d3=0;
        if(a[i].x==a[i+1].x) {
            for(j=1;j<=n;j++) {
                if(modul(v[j].x-a[i].x)>d1)
                    d1=modul(v[j].x-a[i].x);
                if(v[j].y>max(a[i].y,a[i+1].y) && v[j].y-max(a[i].y,a[i+1].y)>d2)
                    d2=v[j].y-max(a[i].y,a[i+1].y);
                if(v[j].y<min(a[i].y,a[i+1].y) && min(a[i].y,a[i+1].y)-v[j].y>d3)
                    d3=min(a[i].y,a[i+1].y)-v[j].y;
            }
            if((double)1LL*(0LL+d2+d3+modul(a[i].y-a[i+1].y))*d1<sol)
                sol=(double)1LL*(0LL+d2+d3+modul(a[i].y-a[i+1].y))*d1;
        }
        else {
            A=(double)(a[i+1].y-a[i].y)/(a[i+1].x-a[i].x);
            B=-1;
            C=(double)(a[i].y-A*a[i].x);
            if(egal(A,0))
                AA=INF;
            else {
                AA=(double)(-1)/A;
                C1=(double)(a[i].y-AA*a[i].x);
                C2=(double)(a[i+1].y-AA*a[i+1].x);
            }
            for(j=1;j<=n-1;j++) {
                if(dist(A,B,C,v[j])>d1)
                    d1=dist(A,B,C,v[j]);
                if(AA!=INF) {
                    if(egal(dist(AA,-1,C1,v[j])+dist(AA,-1,C2,v[j]),dist2(a[i],a[i+1])))
                        continue;
                    if(dist(AA,-1,C1,v[j])<dist(AA,-1,C2,v[j])) {
                        if(dist(AA,-1,C1,v[j])>d2)
                            d2=dist(AA,-1,C1,v[j]);
                    }
                    else if(dist(AA,-1,C2,v[j])>d3)
                        d3=dist(AA,-1,C2,v[j]);
                }
                else {
                    if(egal(modul(a[i].x-v[j].x)+modul(a[i+1].x-v[j].x),dist2(a[i],a[i+1])))
                        continue;
                    if(modul(a[i].x-v[j].x)<modul(a[i+1].x-v[j].x)) {
                        if(modul(a[i].x-v[j].x)>d2)
                            d2=modul(a[i].x-v[j].x);
                    }
                    else if(modul(a[i+1].x-v[j].x)>d3)
                        d3=modul(a[i+1].x-v[j].x);
                }
            }
            if((double)(0LL+d2+d3+1LL*dist2(a[i],a[i+1]))*d1<sol)
                sol=(double)(0LL+d2+d3+1LL*dist2(a[i],a[i+1]))*d1;
        }
    }
    g<<fixed;
    g<<setprecision(2)<<sol;
    return 0;
}