Cod sursa(job #1392169)

Utilizator casuneanu.andreiCasuneanu Andrei Dan casuneanu.andrei Data 18 martie 2015 13:44:41
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.38 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
#define IN "infasuratoare.in"
#define OUT "infasuratoare.out"
#define DMAX 120008

ifstream fin(IN);
ofstream fout(OUT);

struct punct {double x, y;};

int n;
punct st[DMAX];//stiva
int nst;//dim stiva

punct v[DMAX];

void citire();
int det(punct a, punct b, punct c);
bool sortare(const punct &a, const punct &b);
void inf();
void afisare();

int main(){
    citire();
    inf();
    afisare();
    return 0;
}

void afisare(){
    int i;
    fout <<nst<<'\n';

    for (i=1; i<=nst; ++i)
        fout <<fixed<<setprecision(6)<<st[i].x<<' '<<st[i].y<<'\n';

    fout.close();
}

void inf(){
    sort(v+2, v+n+1, sortare);


    st[++nst]=v[1];
    st[++nst]=v[2];

    int i;
    for (i=3; i<=n; ++i){
        //si daca det < 0 atunci nu e bine si scot ultimele doua
        while (det(st[nst-1], st[nst], v[i])<=0 && nst>1)
            --nst;
        st[++nst]=v[i];
    }
}

bool sortare(const punct &a, const punct &b){
    return det(v[1], a, b)>0;
}

int det(punct a, punct b, punct c){
    return a.x*b.y+b.x*c.y+c.x*a.y-(c.x*b.y+a.x*c.y+b.x*a.y);
}

void citire(){
    fin >>n;

    int i;
    for (i=1; i<=n; ++i)
        fin >>v[i].x>>v[i].y;

    int mi=1;
    for (i=2; i<=n; ++i)
        if ((v[i].x < v[mi].x) || (v[i].x==v[mi].x && v[i].y<v[mi].y))
            mi=i;

    punct aux=v[1];
    v[1]=v[mi];
    v[mi]=aux;
}