Cod sursa(job #1571208)

Utilizator cordun_cristinaCristina Maria Cordun cordun_cristina Data 17 ianuarie 2016 15:26:23
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include <fstream>
#include <algorithm>
#include <iomanip>

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

const int NMax = 120005;

pair <double, double> a[NMax], st[NMax];
int n, vf;

void Read()
{
    f>>n;
    for(int i = 1; i <= n; i++) f>>a[i].first>>a[i].second;
}

double Sign(pair <double, double> x, pair <double, double> y, pair <double, double> z)
{
    return (x.first*y.second + y.first*z.second + z.first*x.second - x.second*y.first - y.second*z.first - z.second*x.first);
}

bool Crit(pair <double, double> x, pair <double, double> y)
{
    return Sign(a[1],x,y) > 0;
}

void Solve()
{
    int m = 1;
    vf = 2;
    for(int i = 1; i <= n; i++)
        if(a[i].second < a[m].second || (a[i].second == a[m].second && a[i].first < a[m].first)) m = i;
    swap(a[1],a[m]);
    sort(a+2, a+n+1, Crit);
    st[1] = a[1]; st[2] = a[2];
    for(int i = 3; i <= n; i++)
    {
        while(vf >= 2 && Sign(st[vf-1],st[vf],a[i]) < 0) vf--;
        st[++vf] = a[i];
    }
}

void Print()
{
    g<<vf<<'\n';
    for(int i = 1; i <= vf; i++) g<<fixed<<setprecision(9)<<st[i].first<<' '<<st[i].second<<'\n';
}

int main()
{
    Read();
    Solve();
    Print();
    return 0;
}