Cod sursa(job #1210557)

Utilizator mirceadinoMircea Popoveniuc mirceadino Data 20 iulie 2014 14:29:08
Problema Rubarba Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3 kb
#include<iostream>
#include<fstream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<iomanip>

using namespace std;

typedef pair<int,int> PII;
typedef pair<double,double> PDD;
typedef long long int lld;
const int NMAX = 100000+5;
const int INF = (1<<30);
const double PI = acos(-1.0);

ifstream fin("rubarba.in");
ofstream fout("rubarba.out");

int N,M;
PII P[NMAX];
PII H[NMAX];
double area,sol;

inline lld crossProd(PII A,PII B,PII C)
{
    return (B.first-A.first)*(C.second-A.second)-(C.first-A.first)*(B.second-A.second);
}

inline bool cmp(PII A,PII B)
{
    return crossProd(P[1],A,B)>0;
}

inline PDD rotate(PII A,double alfa)
{
    alfa=2*3.14159-alfa;
    double x,y;
    x=A.first*cos(alfa)-A.second*sin(alfa);
    y=A.first*sin(alfa)+A.second*cos(alfa);
    return make_pair(x,y);
}

inline double dist(PII A,PII B,PII X) // dist(AB,X)
{
    double a=B.second-A.second;
    double b=A.first-B.first;
    double c=B.first*A.second-A.first*B.second;
    return abs(a*X.first+b*X.second+c)/sqrt(a*a+b*b);
}

inline double dist(PII A,double m,PII X) // dist(AB,X), mAB = x
{
    if(m==INF) return abs(A.first-X.first);
    double a=m;
    double b=-1.0;
    double c=-m*A.first+A.second;
    return abs(a*X.first+b*X.second+c)/sqrt(a*a+b*b);
}

inline double panta(PII A,PII B)
{
    if(A.first==B.first) return INF;
    return (1.0*A.second-B.second)/(1.0*A.first-B.first);
}

inline double pantaPerpendiculara(double m)
{
    if(m==0.0) return INF;
    if(m==INF) return 0.0;
    return -1.0/m;
}

void convexHull();

int main()
{
    int i,j,a,b,p,q;
    double m,c,d;
    double xmin,ymin,xmax,ymax;
    PDD Q;

    fin>>N;

    for(i=1; i<=N; i++)
        fin>>P[i].first>>P[i].second;

    convexHull();

    for(i=1; i<=M+1; i++)
        H[M+i]=H[i];

    sol=INF;
    ymin=xmin=INF;
    ymax=xmax=0;

    for(i=1; i<=M; i++)
    {
        if(H[i].second<ymin)
        {
            ymin=H[i].second;
            a=i;
        }
        if(H[i].second>ymax)
        {
            ymax=H[i].second;
            b=i;
        }
        if(H[i].first<xmin)
        {
            xmin=H[i].first;
            p=i;
        }
        if(H[i].first>xmax)
        {
            xmax=H[i].first;
            q=i;
        }
    }

    for(i=a+1,j=b+1; i!=M+a && j!=M+b;)
    {
        d=dist(H[i],H[i-1],H[j-1]);
        m=pantaPerpendiculara(panta(H[i-1],H[i]));
        c=dist(H[p],m,H[q]);
        sol=min(sol,c*d);
        p++;

        d=dist(H[j],H[j-1],H[i]);
        m=pantaPerpendiculara(panta(H[j-1],H[j]));
        c=dist(H[p],m,H[q]);
        i++;
        j++,q++;

        sol=min(sol,c*d);
    }

    fout<<fixed<<setprecision(2)<<sol;

    return 0;
}

void convexHull()
{
    int i;

    sort(P+1,P+N+1);
    sort(P+2,P+N+1,cmp);

    H[++M]=P[1];
    H[++M]=P[2];

    for(i=3; i<=N; i++)
    {
        while(M>=2 && crossProd(H[M-1],H[M],P[i])<0) M--;
        H[++M]=P[i];
    }
}