Cod sursa(job #2089660)

Utilizator valorosu_300Cristian Gherman valorosu_300 Data 16 decembrie 2017 21:53:55
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
const int N = 120002;
const double mic = 1e-12;
int st[N];
bool inStack[N];
struct punct{
    double x,y;
}v[N];
bool cmp(punct a, punct b){
    if(a.x == b.x)
        return a.y < b.y;
    return a.x < b.x;
}
double prod(punct o, punct a, punct b){
    return ((a.x - o.x) * (b.y - o.y) - (b.x - o.x) * (a.y - o.y));
}
void graham(int n){
    int poz = 2, sens = 1;
    sort(v+1, v+n+1, cmp);
    st[1] = 1;
    st[2] = 2;
    inStack[2] = true;
    for(int i=1;i>0;i+=sens){
        if(i == n)
            sens *= -1;
        if(inStack[i] == false){
            while(poz >= 2 && (prod(v[st[poz - 1]], v[st[poz]], v[i]) < mic))
                inStack[st[poz--]] = false;
            st[++poz] = i;
            inStack[i] = true;
        }
    }
    out<<poz - 1<<"\n";
    out<<setprecision(6)<<fixed;
    for(int i=1;i<poz;i++)
        out<<v[st[i]].x<<" "<<v[st[i]].y<<"\n";
}
int main()
{
    int n;
    in>>n;
    for(int i=1;i<=n;i++)
        in>>v[i].x>>v[i].y;
    in.close();
    graham(n);
    out.close();
    return 0;
}