Cod sursa(job #2949693)

Utilizator alexandru_ioan.06Alexandru Ioan alexandru_ioan.06 Data 1 decembrie 2022 14:24:42
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.19 kb
#include <fstream>
#include <algorithm>
#include <stack>
#include <iomanip>

using namespace std;
ifstream cin ("infasuratoare.in");
ofstream cout ("infasuratoare.out");
const int dim = 12e4 + 5;

struct coord 
{
    double lin , col;
}v[dim];
int st[dim];

double Coliniaritate (coord a , coord b , coord c)
{
    return (b.lin - a.lin) * (c.col -a.col) - (b.col - a.col) * (c.lin - a.lin);
}

bool cmp (coord a , coord b)
{
    return (Coliniaritate(v[1] , a , b) < 0);
}

int main()
{
    int n;
    cin >> n;
    int p = 1 ;
    for(int i = 1 ; i <= n ; ++i)
        cin >> v[i].lin >> v[i].col;
    for(int i = 2 ; i <= n ; ++i)
        if(v[i].lin < v[p].lin || (v[i].lin == v[p].lin && v[i].col < v[p].col))
            p = i;
    swap(v[1] , v[p]);
    sort(v+2 , v+n+1 , cmp);
    int k = 0;
    st[++k] = 1 , st[++k] = 2;
    for(int i = 3 ; i <= n ; ++i)
        {
            while(k > 2 && Coliniaritate(v[st[k-1]] , v[st[k]] , v[i]) > 0)
                --k;
            st[++k] = i;
        }
    cout << k << '\n';
    cout << fixed << setprecision(12);
    for(int i = k ; i >= 1 ; --i)
        cout << v[st[i]].lin << ' ' << v[st[i]].col << '\n';
}