Cod sursa(job #2175658)

Utilizator filip.mihalutMihalut Filip filip.mihalut Data 16 martie 2018 18:18:57
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
#include <bits/stdc++.h>
#define Nmax 120002

using namespace std;

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

int n;

struct puncte{
    double x,y;
}v[Nmax];

int i,st[Nmax],vf,semn = 1;
bool seen[Nmax];

inline void read()
{
    f >> n;
    for(i = 1;i <= n;i++)
        f >> v[i].x >> v[i].y;
}

bool cmp(puncte a,puncte b)
{
    if(a.y == b.y)
        return a.x < b.x;
    return a.y < b.y;
}

double determinant(int a,int b,int c)
{
    return v[a].x*v[b].y + v[b].x*v[c].y + v[c].x*v[a].y -
           v[c].x*v[b].y - v[a].x*v[c].y - v[b].x*v[a].y;
}

int main()
{
    read();
    sort(v + 1,v + n + 1,cmp);
    st[1] = 1;
    st[2] = 2;
    vf = 2;
    for(i = 3;i >= 1;i += semn)
    {
        if(seen[i])
           continue;
        while(vf > 1 && determinant(st[vf - 1],st[vf],i) < 0)
            seen[st[vf]] = 0 ,vf--;

        st[++vf] = i; seen[i] = 1;

        if(i == n)
            semn = -1;
    }

    g << vf - 1 << '\n';

    for(i = 1;i < vf;i++)
        g << fixed << setprecision(6) << v[st[i]].x << " " << v[st[i]].y << '\n';
    return 0;
}