Cod sursa(job #2139451)

Utilizator andreistanStan Andrei andreistan Data 22 februarie 2018 16:05:43
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 kb
#include <iostream>
#include <fstream>
#include <iomanip>
#include <algorithm>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
//const double EPS=1e-12;
struct punct
{
    double x, y;
};

punct p[120001];
int st[120001];
bool viz[120001];
int N, H;

void afis()
{
    g << H << '\n';
    g << fixed << setprecision(6);
    for(int i = 1; i <= H; i++)
        g << p[st[i]].x << ' ' << p[st[i]].y << '\n';
}

int compx(const punct &A, const punct &B)
{
    if(A.x == B.x) return A.y < B.y;
    return A.x < B.x;
}

double det(const punct &A, const punct &B, const punct &C)
{
    return (A.x - B.x) * (C.y - A.y) - (A.y - B.y) * (C.x - A.x);
}

int main()
{
    f >> N;
    for(int i = 1; i <= N; i++)
        f >> p[i].x >> p[i].y;
    sort(p + 1, p + N + 1, compx);
    st[1] = 1;
    st[2] = 2;
    viz[2] = 1;
    H = 2;
    for(int i = 3, k = 1; i >= 1; i += k)
    {
        if(viz[i] == 1)
            continue;
        while(H >= 2 && det(p[st[H - 1]], p[st[H]], p[i]) < 0)
        {
            viz[st[H]] = 0;
            H--;
        }
        st[++H] = i;
        viz[i]=1;
        if(i == N)
            k = -1;
    }
    H--;
    afis();
    return 0;
}