Cod sursa(job #2989434)

Utilizator robertrRotaru Stefan Robert robertr Data 6 martie 2023 17:14:09
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.3 kb
#include <algorithm>
#include <iomanip>
#include <fstream>

#define x first
#define y second

using namespace std;

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

typedef double TElem;

typedef pair<TElem, TElem> Point;

const int N_MAX = 120005;
const double EPS = 1e-12;

int N, head;
Point v[N_MAX];
int stack[N_MAX];
bool vis[N_MAX];

void write();

void read() {
    f >> N;
    for(int i = 1; i <= N; ++i) {
        Point p;
        f >> p.x >> p.y;
        v[i] = p;
    }
}

inline TElem cross_product(Point O, Point A, Point B) {
    return (A.x - O.x) * (B.y - O.y) - (B.x - O.x) * (A.y - O.y);
}

void solve() {
    read();

    sort(v+1, v+N+1);

    stack[1] = 1, stack[2] = 2, head = 2;
    vis[2] = true;

    for(int i = 1, p = 1; i > 0; i += (p = (i == N? -p:p))) {
        if(vis[i]) continue;
        while(head >= 2 && cross_product(v[stack[head-1]], v[stack[head]], v[i]) < EPS) {
            vis[stack[head--]] = false;
        }
        stack[++head] = i;
        vis[i] = 1;
    }

    write();
}

void write() {
    g << head - 1 << '\n';
    g << setprecision(6) << fixed;
    for(int i = 1; i < head; ++i) {
        g << v[stack[i]].x << " " << v[stack[i]].y << '\n';
    }
}

int main(void) {
    solve();
}