Cod sursa(job #1833511)

Utilizator Athena99Anghel Anca Athena99 Data 22 decembrie 2016 15:28:05
Problema Rubarba Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.58 kb
#include <algorithm>
#include <cmath>
#include <fstream>
#include <iomanip>
#include <vector>

using namespace std;

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

const double inf= 0x3f3f3f3;
const int nmax= 100000;
const int out_precision= 2;

struct str {
     double x, y;
} v[nmax+1];

vector <int> hull;

inline double area( str x, str y, str z ) {
     double ans= (double)((y.x-x.x)*(z.y-x.y)-(z.x-x.x)*(y.y-x.y))/2;
     return ans;
}

inline double dist( str x, str y ) {
     double ans= sqrt((double)(x.x-y.x)*(x.x-y.x)+(x.y-y.y)*(x.y-y.y));
     return ans;
}

inline double av( double x ) {
     if ( x<0 ) {
          x= -x;
     }
     return x;
}

bool cmp( str x, str y ) {
     return area(v[1], x, y)<0;
}

int main(  ) {
     int n, pos= 1;
     fin>>n;
     if ( n<=2 ) {
          fout<<"0.00\n";
          return 0;
     }

     for ( int i= 1; i<=n; ++i ) {
          fin>>v[i].x>>v[i].y;
          if ( v[i].y<v[pos].y ) {
               pos= i;
          }
     }
     str aux= v[1];
     v[1]= v[pos], v[pos]= aux;
     sort( v+2, v+n+1, cmp );

     hull.push_back(1);
     for ( int i= 2; i<=n; ++i ) {
          for ( ; (int)hull.size()>=2 && area(v[hull[(int)hull.size()-2]], v[hull[(int)hull.size()-1]], v[i])>0; hull.pop_back() ) ;
          hull.push_back(i);
     }
     hull.push_back(1);

     double sol= inf;
     for ( int i= (int)hull.size()-1; i>=1; --i ) {
          double m= inf, p= inf, h= 0, d= dist(v[hull[i]], v[hull[i-1]]);
          str nr1, nr2, x;
          nr1.x= 0, nr1.y= -inf, nr2.x= 0, nr2.y= inf;
          if ( v[hull[i]].x!=v[hull[i-1]].x ) {
               m= (v[hull[i]].y-v[hull[i-1]].y)/(v[hull[i]].x-v[hull[i-1]].x);
               p= (v[hull[i]].y*v[hull[i-1]].x-v[hull[i]].x*v[hull[i-1]].y)/(v[hull[i-1]].x-v[hull[i]].x);
          }

          for ( int j= 1; j<(int)hull.size(); ++j ) {
               h= max(h, (double)av(area(v[hull[i]], v[hull[i-1]], v[hull[j]]))*2/d );
               if ( m!=inf ) {
                    x.x= ((double)v[hull[j]].x+v[hull[j]].y*m-m*p)/(m*m+1), x.y= ((double)v[hull[j]].x*m+v[hull[j]].y*m*m+p)/(m*m+1);
               } else {
                    x.x= v[hull[i]].x, x.y= v[hull[j]].y;
               }

               if ( x.y>nr1.y ) {
                    nr1= x;
               }
               if ( x.y<nr2.y ) {
                    nr2= x;
               }
          }

          sol= min(sol, (double)dist(nr1, nr2)*h );
     }

     fout<<setprecision(out_precision)<<fixed;
     fout<<sol<<"\n";

     return 0;
}