Cod sursa(job #113420)

Utilizator VmanDuta Vlad Vman Data 9 decembrie 2007 23:51:05
Problema Rubarba Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.89 kb
using namespace std;
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

#define Nmax 100005

struct punct { int x,y; };

int N;
int inf[Nmax],nr;
double Smax;
punct P[Nmax];

inline double modul(double a) { return a>=0?a:-a; }

void citire()
{
 int i;
 freopen("rubarba.in","r",stdin);
 scanf("%d",&N);
 for (i=1;i<=N;++i)
     scanf("%d %d",&P[i].x,&P[i].y);
 fclose(stdout);
}

void qsort(int st,int dr)
{
 int i=st,j=dr;
 punct m=P[(st+dr)>>1],aux;
 while (i<=j)
       {
        while ( (double)(P[i].x-P[1].x)/(P[i].y-P[1].y)>(double)(m.x-P[1].x)/(m.y-P[1].y) ) ++i;
        while ( (double)(P[j].x-P[1].x)/(P[j].y-P[1].y)<(double)(m.x-P[1].x)/(m.y-P[1].y) ) --j;
        if (i<=j)
           {
            aux=P[i];
            P[i]=P[j];
            P[j]=aux;
            ++i;
            --j;
           }
       }
 if (i<dr) qsort(i,dr);
 if (st<j) qsort(st,j);
}

int intoarcere(int A,int B,int C)
{
 int aa,bb,cc;
 aa=P[A].y-P[B].y;
 bb=P[B].x-P[A].x;
 cc=P[A].x*P[B].y-P[B].x*P[A].y;
 if (aa*P[C].x+bb*P[C].y+cc<=0) return 1;
 return 0;
}

void infasuratoare()
{
 int i,start=1;
 punct aux;
 for (i=2;i<=N;++i)
      if ( (P[i].y<P[start].y) || ( (P[i].y==P[start].y) && (P[i].x<P[start].x) ) )
         start=i;
 aux=P[1];P[1]=P[start];P[start]=aux;
 start=1;
 for (i=2;i<=N;++i)
    	if (P[i].y==P[1].y)
          	{
                 ++start;
                 aux=P[i];
                 P[i]=P[start];
                 P[start]=aux;
                }
 qsort(start+1,N);
 nr=3;
 inf[1]=1;inf[2]=2;inf[3]=3;
 i=4;
 while (i<=N)
       {
        inf[++nr]=i;
        while ( (nr>3)&&(intoarcere(inf[nr-2],inf[nr-1],inf[nr])) ) inf[--nr]=i;
        ++i;
       }
 for (i=1;i<=nr;++i)
    	P[i]=P[inf[i]];
 P[nr+1]=P[1];
}

void aria()
{
 int i,j;
 double d,S,x,h,d1,d2;
 double hmax,min,max;
 for (i=1;i<=nr;++i)
      {
       d=sqrt( (P[i].x-P[i+1].x)*(P[i].x-P[i+1].x)+(P[i].y-P[i+1].y)*(P[i].y-P[i+1].y) );
       hmax=0;
       min=0;
       max=d;
       for (j=1;j<=nr;++j)
           {
            S=P[i].x*P[i+1].y+P[i+1].x*P[j].y+P[j].x*P[i].y-P[i].y*P[i+1].x-P[i+1].y*P[j].x-P[j].y*P[i].x;
            h=S/d;h=modul(h);
            hmax=h>hmax?h:hmax;
            x=(P[i].x-P[j].x)*(P[i].x-P[j].x)+(P[i].y-P[j].y)*(P[i].y-P[j].y);
            d1=sqrt(x-h*h);
            x=(P[i+1].x-P[j].x)*(P[i+1].x-P[j].x)+(P[i+1].y-P[j].y)*(P[i+1].y-P[j].y);
            d2=sqrt(x-h*h);
            if (modul(d1+d2-d)<0.00000001) continue;
            if (d1<d2) min=min<-d1?min:-d1;
               else max=max>d1?max:d1;
           }
       if ((max-min)*hmax<Smax) Smax=(max-min)*hmax;
      }
}

int main()
{
 citire();
 if (N>2)
 {
 infasuratoare();
 Smax=1000000*10000000;
 aria();
 }
 else Smax=0;
 freopen("rubarba.out","w",stdout);
 printf("%.2f",Smax);
 fclose(stdout);
 return 0;
}