Cod sursa(job #1537680)

Utilizator enedumitruene dumitru enedumitru Data 27 noiembrie 2015 19:30:35
Problema Rubarba Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.67 kb
#include <cstdio>
#include <cmath>
#include <algorithm>
#define Nmax 100010
#define inf 100000000000000.0
#define VMAX 1000000
using namespace std;
int n,m;
double sol=inf;
struct punct {double x,y;} A[Nmax],Hull[Nmax];
inline bool cmp(const punct &P, const punct &Q)
{   return atan2(P.y-A[1].y,P.x-A[1].x)<atan2(Q.y-A[1].y,Q.x-A[1].x);}
inline double det(const punct &A, const punct &B, const punct &C)
{   return 1LL*A.x*B.y+1LL*B.x*C.y+1LL*C.x*A.y-1LL*A.x*C.y-1LL*B.x*A.y-1LL*C.x*B.y;}
void get_hull()
{   int i,p=1;
    for(i=2;i<=n;i++)
        if(A[i].x<A[p].x||(A[i].x==A[p].x && A[i].y<A[p].y)) p=i;
    swap(A[1], A[p]);
    sort(A+2,A+n+1,cmp);
    Hull[1]=A[1]; Hull[2]=A[2]; m=2;
    for(i=3;i<=n;i++)
    {   //verific daca punctul curent este pe ultima latura a infasuratorii
        if(!(det(A[i],Hull[m],Hull[m-1])==0&&min(Hull[m].x,Hull[m-1].x)<=A[i].x&&A[i].x<=max(Hull[m].x,Hull[m-1].x)))
            Hull[++m]=A[i];
         while(m>2&&det(Hull[m-2],Hull[m-1],Hull[m])<=0) {swap(Hull[m-1],Hull[m]); m--;}
    }
    n=m;
    for(i=1;i<=n; i++) A[i]=Hull[i];
}
inline double dist(punct A, punct B) {return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));}
inline double dist_line(punct A, punct B, double m)
{   //dreapta fata de care trebuie sa gasesc distanta are tangenta m si trece prin B
    //cazuri speciale: m = 0 sau m = inf
    if(m==0) return fabs(A.y-B.y);
    if(m==inf) return fabs(A.x-B.x);
    double n=B.y-m*B.x;
    punct C; C.x=B.x+1; C.y=C.x*m+n;
    double h=det(A,B,C)/dist(B,C);
    if(h<0) h=-h;
    return h;
}
inline int next(int i) {return (i<n)?(i+1):1;}
inline double inv(double m)
{   if(m==0) return inf;
    if(m==inf) return 0;
    return -1.0/m;
}
void solve()
{   get_hull(); //algoritm O(n^2)
    int i,j,nxt;
    for(i=1;i<=n;i++)
    {   nxt=next(i);
        double m;
        if(A[i].x==A[nxt].x) m=inf; else m=1.0*(A[nxt].y-A[i].y)/(A[nxt].x-A[i].x);
        int left=i,up=i,right=i; //gasesc up si left
        for(j=next(i);j!=i;j=next(j))
        {   if(dist_line(A[j],A[i],m)>dist_line(A[up],A[i],m)) up=j;
            if(dist_line(A[j],A[i],inv(m))>dist_line(A[left],A[i],inv(m))) left=j;
        }
        for(j=next(left);j!=left;j=next(j))
            if(dist_line(A[j],A[left],inv(m))>dist_line(A[right],A[left],inv(m))) right=j;
        double current_sol = dist_line(A[up], A[i], m)*dist_line(A[left],A[right],inv(m));
        if(current_sol<sol) sol=current_sol;
    }
    printf("%.2lf\n",sol);
}
int main()
{   freopen("rubarba.in", "r", stdin); freopen("rubarba.out", "w", stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%lf %lf",&A[i].x,&A[i].y);
    solve(); return 0;
}