Cod sursa(job #457565)

Utilizator vladiiIonescu Vlad vladii Data 20 mai 2010 09:13:52
Problema Rubarba Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 6.89 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;
long 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 = inf2, yM = inf2;
    
    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);
         
         Puncte susmax = P[S[i]], susmin = P[S[i]];
         x0 = 0;
         y01 = susmax.y - (LD)panta*(susmax.x - x0);
         y02 = susmin.y - (LD)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 - (LD)panta*(aux3.x - x1);
              if(y1 - y01 > 0.00000000) {
                   //se afla deasupra
                   susmax = P[S[j]];
                   y01 = susmax.y - (LD)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 - (LD)panta*(aux3.x - x1);
              if(y1 - y02 < 0.00000000) {
                   //se afla dedesubt
                   susmin = P[S[j]];
                   y02 = susmin.y - (LD)panta*(susmin.x - x0);
              }
         }
         //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 stmax = P[S[i]], drmax = P[S[i]];
         x0 = 0;
         y01 = stmax.y - (LD)pantaperp*(stmax.x - x0);
         y02 = drmax.y - (LD)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 - (LD)pantaperp*(aux3.x - x1);
              if(y1 - y01 < 0.00000000) {
                   //se afla in stinga
                   stmax = P[S[j]];
                   y01 = stmax.y - (LD)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 - (LD)pantaperp*(aux3.x - x1);
              if(y1 - y02 > 0.00000000) {
                   //se afla in dreapta
                   drmax = P[S[j]];
                   y02 = drmax.y - (LD)pantaperp*(drmax.x - x0);
              }
         }
         Pcte cstjos, cstsus, cdrjos;
         //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 = (LD)((LD)x0*panta - y0 + y1 - (LD)x1*pantaperp) / (panta - pantaperp);
         cdrjos.y = y0 + (LD)(cdrjos.x - x0)*panta;
         //coltul stinga jos
         x0 = susmin.x; y0 = susmin.y;
         x1 = stmax.x; y1 = stmax.y;
         cstjos.x = (LD)((LD)x0*panta - y0 + y1 - (LD)x1*pantaperp) / (panta - pantaperp);
         cstjos.y = y0 + (LD)(cstjos.x - x0)*panta;
         //coltul stinga sus
         x0 = susmax.x; y0 = susmax.y;
         x1 = stmax.x; y1 = stmax.y;
         cstsus.x = (LD)((LD)x0*panta - y0 + y1 - (LD)x1*pantaperp) / (panta - pantaperp);
         cstsus.y = y0 + (LD)(cstsus.x - x0)*panta;
         //calculez aria
         long double dist1, dist2;
         dist1 = (LD)(cdrjos.x - cstjos.x)*(cdrjos.x - cstjos.x) / 100 + (LD)(cdrjos.y - cstjos.y)*(cdrjos.y - cstjos.y) / 100;
         dist1 = sqrt(dist1);
         dist2 = (LD)(cstsus.x - cstjos.x)*(cstsus.x - cstjos.x) / 100 + (LD)(cstsus.y - cstjos.y)*(cstsus.y - cstjos.y) / 100;
         dist2 = sqrt(dist2);
         long double rasp;
         rasp = (LD)(dist1 * dist2);
         HMAX = min(HMAX, rasp);
    }
    //fprintf(f2, "%llf", HMAX);
    //fprintf(f2, "%lf", HMAX);
    f2.setf(ios::fixed,ios::floatfield);
    f2.precision(2);
    if(HMAX - floor(HMAX) < 0.001) {
         long long res = (long long)HMAX;
         f2<<res*100<<"\n";
    }
    else {
         f2<<HMAX*100<<"\n";
    }
    fclose(f1); f2.close();
    return 0;
}