Cod sursa(job #3301029)

Utilizator christalknightChristian Micea christalknight Data 20 iunie 2025 22:56:05
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.73 kb
// https://infoarena.ro/problema/infasuratoare

#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>  // for setprecision

using namespace std;

typedef pair <double, double> point_t;

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

const int MAXN = 120005;

int n, head;
point_t v[MAXN];
point_t stack[MAXN];

int cmp_func(point_t& p1, point_t& p2) {
    return cross_product(v[1], p1, p2) < 0;
}
void read(void);
double cross_product(point_t& A, point_t& B, point_t& C);
void sort_points(void);
void convex_hull(void);
void write(void);

int main() {
    read();
    convex_hull();
    write();

    fin.close();
    fout.close();
    return 0;
}

void read(void) 
{
    fin >> n;

    for (int i = 1; i <= n; i++)
        fin >> v[i].first >> v[i].second;
}

void convex_hull(void) 
{
    sort_points();

    stack[1] = v[1];
    stack[2] = v[2];
    head = 2;
    for (int i = 3; i <= n; ++i) {
        while (head >= 2 && cross_product(stack[head - 1], stack[head], v[i]) > 0)
            head--;
        head++;
        // stack[++head] = v[i];
        stack[head] = v[i];
    }
}

void sort_points(void) 
{
    int pos = 1;

    for (int i = 2; i <= n; ++i)
        if (v[i] < v[pos])
            pos = i;
    
    swap(v[1], v[pos]);
    sort(v + 2, v + n + 1, cmp_func);
}

double cross_product(point_t& A, point_t& B, point_t& C)
{
    return (B.first - A.first) * (C.second - A.second) - (B.second - A.second) * (C.first - A.first);
}

void write(void) 
{
    fout << fixed;
    fout << head << "\n";
    for (int i = head; i >= 1; i--)
        fout << setprecision(9) << stack[i].first << " " << stack[i].second << "\n";
}