Cod sursa(job #256130)

Utilizator mihai_floreaFlorea Mihai Alexandru mihai_florea Data 11 februarie 2009 10:34:49
Problema Rubarba Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.22 kb
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
const int NMAX=100005;
struct punct{
       double x,y;
       };
int N,st[NMAX],H;
punct a[NMAX],O;
double prod_vec(punct A,punct O,punct B){
       return (A.x-O.x)*(B.y-O.y)-(B.x-O.x)*(A.y-O.y);
       }
int cmp(punct A,punct B){
    return prod_vec(A,O,B)>0;
    }
void read(){
     freopen("rubarba.in","r",stdin);
     scanf("%d",&N);
     int i,x,y;
     for (i=1;i<=N;++i){
         scanf("%d %d",&x,&y);
         a[i].x=x;
         a[i].y=y;}
     }
void convex_hull(){
     //determinam O = punctul cel mai de jos si in caz de egalitate cel mai din stanga
     int i,j;
     O=a[1];j=1;
     for (i=2;i<=N;++i)
       if (a[i].y<O.y || (a[i].y==O.y && a[i].x<O.x))
         O=a[i],j=i;
     punct aux=a[j];a[j]=a[1];a[1]=aux;
     //sortam punctele in functie de unghiul determinat de dreapta oriz ce trece prin O
     sort(a+2,a+N+1,cmp);
     //gasim infasuratoarea convexa
     H=2;st[1]=1;st[2]=2;
     for (i=3;i<=N;++i){
         //cat timp ultimele doua puncte din stiva impreuna cu punctul curent 
         //nu formeaza o "intoarcere la dreapta" ...
         while (H>=2 && prod_vec(a[st[H-1]],a[st[H]],a[i])>=0) H--;
         st[++H]=i;
         }
     if (prod_vec(a[st[H-1]],a[st[H]],a[1])==0) --H;
     }
punct b[NMAX]; //punctele de pe infasuratoarea convexa
double prod_scalar(punct A,punct O,punct B){
       //(x1*i+y1*j)*(x2*i+y2*j)=x1*x2+y1*y2
       return (A.x-O.x)*(B.x-O.x)+(A.y-O.y)*(B.y-O.y);
       }
double dist(punct A,punct B){
       return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));
       }
void solve(){
     int i,j;
     double sol=1.e12;
     freopen("rubarba.out","w",stdout);
     for (i=1;i<=H;++i) b[i]=a[st[i]];
     /*
     prod_vec(A,O,B)=OA*OB*sin(AOB)  ,unghi masurat in sens trigonometric
     
     Rotim planul in jurul punctului b[i] in sens antitrigonometric cu un unghi egal
     cu unghiul facut de dreapta orizontala ce trece prin O si dreapta determinata
     de punctele b[i] si b[i+1] (b[H+1]=b[1])
     
     Formula roatatiei punctului A in jurul punctului O cu t grade in sens trigonometric:
       A'-O = (A-O) * (cos t + i*sin t) 
       A'.x + i*A'.y - O.x - i*O.y =(A.x - O.x +i*(A.y-O.y))*(cos t + i*sin t)
       A'.x-O.x + i*(A'.y-O.y) = (A.x- O.x)* cos t -(A.y-O.y)*sin t +
                                  i*( (A.x-O.x)*siThe Oh! n t + (A.y-O.y)*cos t) )
       Deci:
       A'.x = O.x + (A.x - O.x)*cos t - (A.y - O.y)*sin t
       A'.y = O.y + (A.x - O.x)*sin t + (A.y - O.y)*cos t
       
       sin e impara: sin(-x)=-sin(x)
       cos e para: cos(-x)=cos x
       Roatia in sens antitrigonometric cu t grade este roatia in sens 
       trigonometric cu -t grade
       
     prod_scalar(A,O,B)=OA*OB*cos(AOB)
                                 
     */
     punct Q;
     double xmax,xmin,ymax,ymin;
     double cost,sint;
     for (i=1;i<=H;++i){
       //translatam punctele pentru a evita depasiri
       xmin=b[1].x;
       ymin=b[1].y;
       for (j=2;j<=H;++j){
           xmin=min(xmin,b[j].x);
           ymin=min(ymin,b[j].y);
           }
       for (j=1;j<=H;++j){
           b[j].x-=xmin;
           b[j].y-=ymin;
           }
       
       b[H+1]=b[1];
       //determinam unghiul de rotatie
       Q=b[i];
       Q.x=b[i].x+1;
       double prod_lat=dist(b[i],b[i+1]); //dist(b[i],Q)=1  

       cost=prod_scalar(Q,b[i],b[i+1])/prod_lat;
       sint=-(prod_vec(Q,b[i],b[i+1])/prod_lat);
       
       
       //rotim
       for (j=1;j<=H;++j){
         if (i==j) continue;
         double xx=b[j].x-b[i].x;
         double yy=b[j].y-b[i].y;
         b[j].x = b[i].x + xx*cost - yy*sint;
         b[j].y = b[i].y + xx*sint + yy*cost;
         }
       //determinam xmax,ymax,xmin,ymin
       xmin=xmax=b[1].x;
       ymin=ymax=b[1].y;
       for (j=2;j<=H;++j){
           xmin=min(xmin,b[j].x);
           xmax=max(xmax,b[j].x);
           ymin=min(ymin,b[j].y);
           ymax=max(ymax,b[j].y);
           }
       double arie=(xmax-xmin)*(ymax-ymin);
       sol=min(sol,arie);
       }   
     printf("%.2lf",sol);
    
     }
int main(){
    read();
    convex_hull();
    solve();
    return 0;
}