Cod sursa(job #2110623)

Utilizator leraValeria lera Data 20 ianuarie 2018 23:02:22
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.36 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
#define Nmax 120005

using namespace std;

ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");

int N, j;
pair<double, double>p[Nmax];
pair<double, double>st[Nmax];

bool cmp(pair<double, double> a, pair<double, double> b)
{
    if(a.first == b.first)return a.second < b.second;
    return a.first < b.first;
}
double determ(pair<double, double> a, pair<double, double> b, pair<double, double>c)
{
    return ((a.first - c.first)*(b.second - c.second) + (b.first - c.first)*(c.second - a.second));
}
int main()
{
    fin >> N;
    for(int i = 1; i <= N; i++)
        fin >> p[i].first >> p[i].second;
    sort(p + 1, p + N + 1, cmp);

    st[1].first = p[1].first;
    st[1].second = p[1].second;
    j = 1;

    for(int i = 2; i <= N; i++)
    {
        while(j > 1 && determ(st[j - 1], st[j], p[i]) > 0)
            j--;
        j++;
        st[j].first = p[i].first;
        st[j].second = p[i].second;

    }
    for(int i = N - 1; i >= 1; i--)
    {
        while(j > 1 && determ(st[j - 1], st[j], p[i]) > 0)
            j--;
        j++;
        st[j] = p[i];
    }
    j--;
    fout << j << '\n';
    for(int i = j; i >= 1; i--)
        fout << fixed << setprecision(6) << st[i].first << " " << st[i].second << '\n';
    return 0;
}