Cod sursa(job #457573)

Utilizator vladiiIonescu Vlad vladii Data 20 mai 2010 09:49:34
Problema Rubarba Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 7.9 kb
#include <iostream>
#include <fstream>
#include <iomanip>
#include <math.h>
using namespace std;
#define maxn 100010
#define inf 10000000000000LL
#define inf2 1000010
#define LL long long
#define LD long double

int N;
int S[maxn], varf;
struct Puncte {
    int x, y;
} P[maxn];
struct Pcte {
    long double x, y;
} aux1, aux2, aux3;
double HMAX;

LL Produs(Puncte P1, Puncte P2, Puncte P3) {
    return (LL)P2.x*P3.y - (LL)P2.x*P1.y - (LL)P1.x*P3.y + (LL)P1.x*P1.y - 
           (LL)P3.x*P2.y + (LL)P3.x*P1.y + (LL)P1.x*P2.y - (LL)P1.x*P1.y;
}

int cmp(Puncte a, Puncte b) {
    if((LL)(a.x-P[1].x)*(b.y-P[1].y) != (LL)(b.x-P[1].x)*(a.y-P[1].y)) {
         return (LL)(a.x-P[1].x)*(b.y-P[1].y) > (LL)(b.x-P[1].x)*(a.y-P[1].y);
    }
    else if(P[1].y==a.y && P[1].y==b.y) {
         return (LL)(a.x-P[1].x)*(a.x-P[1].x) + (LL)(a.y-P[1].y)*(a.y-P[1].y) <
                (LL)(b.x-P[1].x)*(b.x-P[1].x) + (LL)(b.y-P[1].y)*(b.y-P[1].y);
    }
    else if(!Produs(a, b, P[1])) {
          return a.x < b.x;
    }
}

void POP() {
    varf--;
}

void PUSH(int a) {
    varf++;
    S[varf]=a;
}

int main() {
    FILE *f1=fopen("rubarba.in", "r"); fstream f2; f2.open("rubarba.out", ios::out);
    int i, j, p, q;
    int xM = inf, yM = inf;
    
    fscanf(f1, "%d\n", &N);
    for(i=1; i<=N; i++) {
         fscanf(f1, "%d %d\n", &p, &q);
         P[i].x = p; P[i].y = q;
         if(P[i].y < yM) { yM = P[i].y; xM = P[i].x; j=i; }
         else if(P[i].y == yM && P[i].x < xM) { xM = P[i].x; j=i; }
    }
    //infasuratoare convexa
    swap(P[1], P[j]);
    sort(P+2, P+N+1, cmp);
    
    PUSH(1); PUSH(2);
    for(i=3; i<=N; i++) {
         LL o;
         o=Produs(P[S[varf-1]], P[S[varf]], P[i]);
         if(o==0) { //punctele is coliniare
              PUSH(i);
         }
         else {
              if(o>0) { //intoarcere la stinga - valid
                   PUSH(i);
              }
              else { //intoarcere la dreapta - invalid
                   while(o<0 && varf>1) {
                        POP();
                        o=Produs(P[S[varf-1]], P[S[varf]], P[i]);
                   }
                   PUSH(i);
              }
         }
    }
    int H = varf;
    S[varf + 1] = S[1];
    HMAX = inf;
    for(i=1; i<=H; i++) {
         //panta e data de dreapta (S[i], S[i+1]);
         long double panta, pantaperp;
         long double x, y, x0, y0, x1, y1;
         long double y01, y02;
         
         if(P[S[i]].x == P[S[i+1]].x && panta == inf) continue;
         else if((LD)(P[S[i+1]].y - P[S[i]].y) / (P[S[i+1]].x - P[S[i]].x) == panta) continue;
         
         if(P[S[i]].x == P[S[i+1]].x) panta = inf;
         else panta = (LD)(P[S[i+1]].y - P[S[i]].y) / (P[S[i+1]].x - P[S[i]].x);
         
         //aflu panta perpendicularei
         if(P[S[i]].y == P[S[i+1]].y) pantaperp = inf;
         else pantaperp = - (LD)(P[S[i+1]].x - P[S[i]].x) / (P[S[i+1]].y - P[S[i]].y);
         
         Puncte susmax = P[S[i]], susmin = P[S[i]];
         Puncte stmax = P[S[i]], drmax = P[S[i]];
         Pcte cstjos, cstsus, cdrjos;
         
         if(panta == 0 || pantaperp == 0) {
              //caut pctele      
              for(j=1; j<=H; j++) {
                   if(P[S[j]].y > susmax.y) {
                        susmax = P[S[j]];
                   }
                   if(P[S[j]].y < susmin.y) {
                        susmin = P[S[j]];
                   }
              }
              for(j=1; j<=H; j++) {
                   if(P[S[j]].x < stmax.x) {
                        stmax = P[S[j]];
                   }
                   if(P[S[j]].x > drmax.x) {
                        drmax = P[S[j]];
                   }
              }
              cstsus.x = stmax.x;
              cstsus.y = susmax.y;
              cstjos.x = stmax.x;
              cstjos.y = susmin.y;
              cdrjos.x = drmax.x;
              cdrjos.y = susmin.y;
         }
         else {
              x0 = 0;
              y01 = susmax.y - panta*(susmax.x - x0);
              y02 = susmin.y - panta*(susmin.x - x0);
              for(j=1; j<=H; j++) {
                   //vad unde intersecteaza axa Oy
                   //aflu susmax
                   //determin ecuatia dreptei
                   //verific daca S[j] se afla deasupra
                   aux3.x = P[S[j]].x; aux3.y = P[S[j]].y;
                   x1 = 0;
                   y1 = aux3.y - panta*(aux3.x - x1);
                   if(y1 - y01 > 0.00000000) {
                         //se afla deasupra
                         susmax = P[S[j]];
                         y01 = susmax.y - panta*(susmax.x - x0);
                   }
                   //aflu susmin
                   //determin ecuatia dreptei
                   aux3.x = P[S[j]].x; aux3.y = P[S[j]].y;
                   x1 = 0;
                   y1 = aux3.y - panta*(aux3.x - x1);
                   if(y1 - y02 < 0.00000000) {
                        //se afla dedesubt
                        susmin = P[S[j]];
                        y02 = susmin.y - panta*(susmin.x - x0);
                   }
              }
         
              x0 = 0;
              y01 = stmax.y - pantaperp*(stmax.x - x0);
              y02 = drmax.y - pantaperp*(drmax.x - x0);
              for(j=1; j<=H; j++) {
                   //aflu srmax
                   //determin ecuatia dreptei
                   //verific daca S[j] se afla in stinga
                   aux3.x = P[S[j]].x; aux3.y = P[S[j]].y;
                   x1 = 0;
                   y1 = aux3.y - pantaperp*(aux3.x - x1);
                   if(y1 - y01 < 0.00000000) {
                        //se afla in stinga
                        stmax = P[S[j]];
                        y01 = stmax.y - pantaperp*(stmax.x - x0);
                   }
                   //aflu drmax
                   //determin ecuatia dreptei
                   aux2.x = x0; aux2.y = y0;
                   //verific daca S[j] se afla in dreapta
                   aux3.x = P[S[j]].x; aux3.y = P[S[j]].y;
                   x1 = 0;
                   y1 = aux3.y - pantaperp*(aux3.x - x1);
                   if(y1 - y02 > 0.00000000) {
                        //se afla in dreapta
                        drmax = P[S[j]];
                        y02 = drmax.y - pantaperp*(drmax.x - x0);
                   }
              }
              //acum stiu pctele de extrem si pantele dreptelor
              //coltul dreapta jos
              x0 = susmin.x; y0 = susmin.y;
              x1 = drmax.x; y1 = drmax.y;
              cdrjos.x = (x0*panta - y0 + y1 - x1*pantaperp) / (panta - pantaperp);
              cdrjos.y = y0 + (cdrjos.x - x0)*panta;
              //coltul stinga jos
              x0 = susmin.x; y0 = susmin.y;
              x1 = stmax.x; y1 = stmax.y;
              cstjos.x = (x0*panta - y0 + y1 - x1*pantaperp) / (panta - pantaperp);
              cstjos.y = y0 + (cstjos.x - x0)*panta;
              //coltul stinga sus
              x0 = susmax.x; y0 = susmax.y;
              x1 = stmax.x; y1 = stmax.y;
              cstsus.x = (x0*panta - y0 + y1 - x1*pantaperp) / (panta - pantaperp);
              cstsus.y = y0 + (cstsus.x - x0)*panta;
              //calculez aria
         }
         double dist1, dist2;
         dist1 = (cdrjos.x - cstjos.x)*(cdrjos.x - cstjos.x) + (cdrjos.y - cstjos.y)*(cdrjos.y - cstjos.y);
         dist1 = sqrt(dist1);
         dist2 = (LD)(cstsus.x - cstjos.x)*(cstsus.x - cstjos.x) + (LD)(cstsus.y - cstjos.y)*(cstsus.y - cstjos.y);
         dist2 = sqrt(dist2);
         double rasp;
         rasp = (dist1 * dist2);
         //cout<<dist1<<" "<<dist2<<" "<<rasp<<endl;
         HMAX = min(HMAX, rasp);
    }
    //fprintf(f2, "%llf", HMAX);
    //fprintf(f2, "%lf", HMAX);
    f2.setf(ios::fixed,ios::floatfield);
    f2.precision(2);
    f2<<HMAX<<"\n";
    fclose(f1); f2.close();
    return 0;
}