Cod sursa(job #1918133)

Utilizator filip.mihalutMihalut Filip filip.mihalut Data 9 martie 2017 14:14:47
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.18 kb
#include <iostream>
#include <fstream>
#include <stack>
#include <algorithm>
#include <iomanip>

using namespace std;

ifstream f ("infasuratoare.in");
ofstream g ("infasuratoare.out");

pair < double,double > v[120005];
bool ok;
int st[120005];
int x,n,i , poz,vf;

double unghi(const pair < int,int >  &a,const pair < int,int >  &b,pair < int,int >  c)
{
    return (b.first - a.first) * (c.second - a.second) - (b.second - a.second) * (c.first - a.first);;
}

bool cmp(const pair<int,int > &a,const pair < int,int > &b)
{
     return (unghi(v[1],a,b) < 0);
}

int main()
{
    f >> n;
    poz = 1;
    for(i = 1; i <= n; i++)
    {
        f >> v[i].first >> v[i].second;
        if(v[poz] > v[i])
            poz = i;
    }
    swap(v[1],v[poz]);
    sort(v + 2,v + n + 1 ,cmp);
    st[1] = 1;
    st[2] = 2;
    vf = 2;
    i = 3;
    while(i <= n)
    {
        while(vf >= 2 && unghi(v[st[vf - 1]],v[st[vf]] , v[i]) > 0)
            vf--;
        st[++vf] = i;
        i++;
    }

    g << vf << '\n';
    g << fixed << setprecision(6) ;
    while(vf)
        g  << v[st[vf]].first << " " << v[st[vf]].second  << '\n' ,vf--;
    return 0;
}