Cod sursa(job #3301031)

Utilizator christalknightChristian Micea christalknight Data 20 iunie 2025 23:00:33
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.09 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]; // input points (indexed starting from position 1)
point_t stack[MAXN]; // convex hull stack

void read(void);
// cross product of vectors AB and AC (orientation test)
double cross_product(point_t& A, point_t& B, point_t& C);
// sorts points by polar angle with respect to the lowest (leftmost) point
void sort_points(void);
// constructs the convex hull using a stack
void convex_hull(void);
// writes the convex hull to output in reverse order
void write(void);
int cmp_func(point_t& p1, point_t& p2) {
    return cross_product(v[1], p1, p2) < 0;
}

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++) {
         // Remove last point while it makes a right turn
        while (head >= 2 && cross_product(stack[head - 1], stack[head], v[i]) > 0)
            head--;
        head++;
        stack[head] = v[i]; // add current point
    }
}

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]); // move pivot to front
    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";
}