Cod sursa(job #391022)

Utilizator vladiiIonescu Vlad vladii Data 4 februarie 2010 22:15:25
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.91 kb
#include <iostream>
#include <fstream>
#include <math.h>
using namespace std;
#define INF 1000000000
int N, varf;
struct Puncte {
    double x;
    double y;
} P[120002], S[120002], aux;

int cmp(Puncte a, Puncte b) {
    return (double)(a.x-P[1].x)*(b.y-P[1].y) > (double)(b.x-P[1].x)*(a.y-P[1].y);
}

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

void POP() {
    varf--;
}

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

int main() {
    FILE *f1=fopen("infasuratoare.in", "r"), *f2=fopen("infasuratoare.out", "w");
    int i, j, p, q;
    double xmin=INF, ymin=INF;
    fscanf(f1, "%d", &N);
    for(i=1; i<=N; i++) {
         fscanf(f1, "%lf%lf", &P[i].x, &P[i].y);
         if(P[i].y<ymin) {
              xmin=P[i].x;
              ymin=P[i].y;
              p=i;
         }
         else if(P[i].y==ymin && P[i].x<xmin) {
              xmin=P[i].x;
              p=i;
         }
    }
    aux=P[1]; P[1]=P[p]; P[p]=aux;
    sort(P+2, P+N+1, cmp);
    PUSH(P[1]); PUSH(P[2]);
    for(i=3; i<=N; i++) {
         //S[varf-1], S[varf], P[i]
         double o=Produs(S[varf-1], S[varf], P[i]);
         if(o==0) {
              //cele 3 pcte is coliniare
              POP();
              PUSH(P[i]);
         }
         else if(o>0) {
              //avem intoarcere la stinga (valida)
              PUSH(P[i]);
         }
         else if(o<0) {
              //avem intoarcere la dreapta
              while(varf>1 && o<=0) {
                   POP();
                   o=Produs(S[varf-1], S[varf], P[i]);
              }
              PUSH(P[i]);
         }
    }
    fprintf(f2, "%d\n", varf);
    for(i=1; i<=varf; i++) {
         fprintf(f2, "%lf %lf\n", S[i].x, S[i].y);
    }
    fclose(f1); fclose(f2);
    return 0;
}