Cod sursa(job #2052289)

Utilizator ciocirlanrCiocirlan Robert ciocirlanr Data 30 octombrie 2017 12:58:24
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.1 kb
#include <fstream>
#include <iomanip>
#include <algorithm>
#define x first
#define y second

using namespace std;
typedef pair<float,float> Punct;

const int NMAX = 120005;
const double INF = 1e-12;

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

int N;
Punct v[NMAX];
bool vis[NMAX];
int st[NMAX],varf;

void citire() {
    in >> N;
    for(int i = 1; i <= N; ++i) in >> v[i].x >> v[i].y;
}

double produs(Punct O, Punct A, Punct B) {
    return (A.x - O.x) * (B.y - O.y) - (B.x - O.x) * (A.y - O.y);
}

void rezolvare() {
    sort(v + 1,v + N + 1);
    st[1] = 1; st[2] = 2; varf = 2;
    vis[2] = 1;

    for(int i = 1, p = 1; i > 0; i+= (p = (i == N ? -p :p))) {
        if(vis[i]) continue;
        while(varf >= 2 and produs(v[st[varf - 1]], v[st[varf]], v[i]) < INF)
            vis[st[varf--]] = 0;
        st[++varf] = i;
        vis[i] = 1;
    }
    out << varf - 1 << '\n';
    out << setprecision(6) << fixed;
    for(int i = 1; i < varf; ++i) out << v[st[i]].x << " " << v[st[i]].y << '\n';
}

int main() {
    citire();
    rezolvare();
}