Cod sursa(job #1583572)

Utilizator cordun_cristinaCristina Maria Cordun cordun_cristina Data 29 ianuarie 2016 01:40:15
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 kb
#include <iomanip>
#include <fstream>
#include <vector>
#include <algorithm>

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

const int Nmax = 120005;
int n, nr;
pair <double, double> P[Nmax];
pair <double, double> Sol[Nmax];

double semn(pair<double, double> A, pair<double, double> B, pair<double, double> C)
{
    return (A.first*B.second + B.first*C.second + C.first*A.second - A.second*B.first - B.second*C.first - C.second*A.first);
}

bool Crit(pair<double, double> A, pair<double, double> B)
{
    return semn(P[1],A,B) > 0;
}

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

void Solve()
{
    int pos = 1;
    for(int i = 2; i <= n; i++)
    {
        if(P[pos].second > P[i].second || (P[pos].second == P[i].second && P[pos].first > P[i].first))
            pos = i;
    }
    swap(P[1], P[pos]);
    sort(P+2, P+n+1, Crit);
    Sol[1] = P[1]; Sol[2] = P[2]; nr = 2;
    for(int i = 3; i <= n; i++)
    {
        while(nr >= 2 && semn(Sol[nr-1], Sol[nr], P[i]) < 0) nr--;
        Sol[++nr] = P[i];
    }
}

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

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