Cod sursa(job #891904)

Utilizator evodaniVasile Daniel evodani Data 25 februarie 2013 21:11:44
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.69 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;
bool egal (double a, double b) { return abs(a-b)<prec; }
bool comp (punct a, punct b) {
    if (!egal(a.u, b.u)) return a.u<b.u;
    else return a.r>b.r;
}
void push (punct a) { stiva[++vf]=a; }
void pop() { --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));
}
double mny, mnx;
int main()
{
    mny=mnx=inf;
    int i; 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; } else if (aux.yy==mny) if (aux.xx<mnx) mnx=aux.xx;
        aux.r=sqrt(aux.xx*aux.xx+aux.yy*aux.yy); aux.u=atan(aux.yy/aux.xx); puncte.push_back(aux);
    }
    sort(puncte.begin(), puncte.end(), comp);
    push(puncte[0]); push(puncte[1]);
    for (i=2; i<n; ++i) {
        o=prod(stiva[vf-1], stiva[vf], puncte[i]);
        if (o>0) push(puncte[i]); //intoarcere la stanga
        else {
            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]);
        }
    }
    fprintf (fout, "%d\n", vf); while (vf) { fprintf (fout, "%lf %lf\n", stiva[vf].xx, stiva[vf].yy); --vf; }
    return 0;
}