Cod sursa(job #2003632)

Utilizator dumitrescu_andreiDumitrescu Andrei dumitrescu_andrei Data 23 iulie 2017 14:25:44
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");

struct Punct {
double x,y;
} a[120001],S[120001];

int n,vf;

double unghi(Punct a, Punct b, Punct c){
    return (b.y - a.y) * (c.x - a.x) - (c.y - a.y) * (b.x - a.x);
}
bool cmp(Punct x, Punct b){
    return (unghi(a[1],x,b) > 0);
}

void PUSH(Punct P)
{
    vf++;
    S[vf]=P;
}

void POP()
{
    vf--;
}


int main()
{
    f>>n;
    for(int i=1;i<=n;++i)
        f>>a[i].x>>a[i].y;
    int poz=1;
    for(int i = 1; i <= n; ++i)
        if(a[i].x < a[poz].x || (a[i].x == a[poz].x && a[i].y < a[poz].y))
            poz = i;
    swap(a[1],a[poz]);
    sort(a + 2, a + n + 1, cmp);
    vf=0;
    PUSH(a[1]);
    PUSH(a[2]);
     for(int i = 3; i <= n; ++i){
        while(vf >= 2 && unghi(S[vf - 1], S[vf], a[i]) < 0)
            --vf;
        PUSH(a[i]);
    }

    g<<vf<<'\n';
    for(int i=vf;i>=1;--i)
        g<<fixed<<setprecision(6)<<S[i].x<<" "<<S[i].y<<'\n';

    return 0;

}