Cod sursa(job #2400524)

Utilizator AlexandruGabrielAliciuc Alexandru AlexandruGabriel Data 8 aprilie 2019 20:30:35
Problema Infasuratoare convexa Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.24 kb
#include <bits/stdc++.h>
#define N 120010

using namespace std;

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

struct punct
{
    long double x, y;
};

int n;
int st[N], top;
punct a[N];

void Citire()
{
    fin >> n;
    for (int i = 1; i <= n; i++)
        fin >> a[i].x >> a[i].y;
}

double prod_Vectorial(punct p, punct m, punct q)
{
    long double y1 = p.y - m.y;
    long double y2 = p.y - q.y;
    long double x1 = p.x - m.x;
    long double x2 = p.x - q.x;
    return y2 * x1 - y1 * x2;
}

bool cmp(punct p, punct q)
{
    return prod_Vectorial(a[1], p, q) > 0;
}

void Sorteaza()
{
    int ind = 1;
    for (int i = 2; i <= n; i++)
        if (a[i].x < a[ind].x)
            ind = i;
    swap(a[1], a[ind]);
    sort(a + 2, a + n + 1, cmp);
}

void Solve()
{
    st[1] = 1;
    st[2] = 2;
    top = 2;

    for (int i = 3; i <= n; i++)
    {
        while (top > 2 && prod_Vectorial(a[st[top - 1]], a[st[top]], a[i]) < 0)
            top--;
        st[++top] = i;
    }

    fout << top << "\n";
    for (int i = 1; i <= top; i++)
        fout << a[st[i]].x << " " << a[st[i]].y << "\n";
}

int main()
{
    Citire();
    Sorteaza();
    Solve();
    return 0;
}