Cod sursa(job #892014)

Utilizator evodaniVasile Daniel evodani Data 25 februarie 2013 21:47:13
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.86 kb
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
#define NMAX 120005
using namespace std;
const double prec = 1e-12;
const double inf=1000000001;
FILE *fin, *fout;
struct punct { double r, u, xx, yy; }aux;
vector <punct> puncte;
punct stiva[NMAX];
int n, vf;
double prod (punct p0, punct p1, punct p2) {
    return ((p1.xx-p0.xx)*(p2.yy-p0.yy)-(p2.xx-p0.xx)*(p1.yy-p0.yy));
}
bool egal (double a, double b) { return abs(a-b)<prec; }
bool comp (punct a, punct b) {
    return prod(puncte[0], a, b)>0; //daca B se afla la stanga lui A, il pun dupa A in vector
    //daca ar exista coliniare, l-as retine pe acela cu distanta mai mare de P[0]
}
void push (punct a) { stiva[++vf]=a; }
void pop() { --vf; }
double mny, mnx;
int main()
{
    mny=mnx=inf;
    int i, poz; double o;
    fin=fopen("infasuratoare.in", "r"); fout=fopen("infasuratoare.out", "w");
    fscanf (fin, "%d", &n);
    for (i=1; i<=n; ++i) {
        fscanf (fin, "%lf%lf", &aux.xx, &aux.yy);
        if (aux.yy<mny) { mny=aux.yy; mnx=aux.xx; poz=i-1; } else if (aux.yy==mny) if (aux.xx<mnx) { mnx=aux.xx; poz=i-1; }
        //aux.r=sqrt(aux.xx*aux.xx+aux.yy*aux.yy); aux.u=atan(aux.yy/aux.xx);
        puncte.push_back(aux);
    }
    swap(puncte[0], puncte[poz]); sort(puncte.begin()+1, puncte.end(), comp);
    push(puncte[0]); push(puncte[1]);
    for (i=2; i<n; ++i) {
        o=prod(stiva[vf-1], stiva[vf], puncte[i]);
        while (o<0 && vf>1) { //scot din stiva toate punctele care fac intoarceri la dreapta cu P[i]
            pop(); o=prod(stiva[vf-1], stiva[vf], puncte[i]);
        }
        push(puncte[i]);
    }
    //for (i=0; i<n; ++i) fprintf (fout, "%lf %lf\n", puncte[i].xx, puncte[i].yy);
    fprintf (fout, "%d\n", vf); while (vf) { fprintf (fout, "%lf %lf\n", stiva[vf].xx, stiva[vf].yy); --vf; }
    fclose(fout); fclose(fin);
    return 0;
}