Cod sursa(job #2176289)

Utilizator zdavid112zIon David-Gabriel zdavid112z Data 16 martie 2018 22:15:52
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb
#include <bits/stdc++.h>

using namespace std;

struct vec2
{
    double x, y;
} v[120005];
int st[120005];

double det(const vec2& a, const vec2& b, const vec2& c)
{
    return (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y);
}

bool cmp(const vec2& a, const vec2& b)
{
    return det(v[1], a, b) > 0;
}

int main()
{
    freopen("infasuratoare.in", "r", stdin);
    freopen("infasuratoare.out", "w", stdout);
    int n, pmin = 1;
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
    {
        scanf("%lf%lf", &v[i].x, &v[i].y);
        if(v[pmin].y > v[i].y || (v[pmin].y == v[i].y && v[pmin].x > v[i].x))
            pmin = i;
    }
    swap(v[1], v[pmin]);
    sort(v + 2, v + 1 + n, cmp);
    st[1] = 1;
    st[2] = 2;
    int lst = 2;
    for(int i = 3; i <= n; i++)
    {
        while(lst >= 2 && det(v[st[lst - 1]], v[st[lst]], v[i]) <= 0)
            lst--;
        st[++lst] = i;
    }
    printf("%d\n", lst);
    for(int i = 1; i <= lst; i++)
        printf("%f %f\n", v[st[i]].x, v[st[i]].y);
    return 0;
}