Cod sursa(job #1642689)

Utilizator secretCCMniciun nume secretCCM Data 9 martie 2016 15:38:22
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.18 kb
#include <iostream>
#include <fstream>
#include <iomanip>
#include <algorithm>

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

const int Nmax = 120005;
int n;
pair <double,double> a[Nmax], st[Nmax];

double sign( pair < double, double > a1, pair < double, double > b, pair < double, double > c)
{
    return a1.first*b.second + b.first*c.second + c.first*a1.second - a1.second*b.first - b.second*c.first - c.second*a1.first;
}

bool crt(pair < double, double > a1, pair < double, double > b)
{
    return sign(a[1], a1, b) > 0;
}

int main()
{
    int m = 1, vf = 2;
    f>>n;
    for(int i = 1; i <= n; i++) f>>a[i].first>>a[i].second;
    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[m],a[1]);
    sort(a+2,a+1+n,crt);
    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];
    }
    g<<vf<<'\n';
    for(int i = 1; i <= vf; i++) g<<fixed<<setprecision(9)<<st[i].first<<' '<<st[i].second<<'\n';
    return 0;
}