Cod sursa(job #3300637)

Utilizator adela_codreanCodrean Adela-Maria adela_codrean Data 18 iunie 2025 11:49:59
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.66 kb
#include <bits/stdc++.h>
using namespace std;
#define MAX 150005

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

int n, stiva[MAX], top, indice_start;
long double xmin, ymin = 1e18L;

struct Punct {
    long double x, y;
} puncte[MAX];


bool comp(const Punct &a, const Punct &b) {
    return a.x * b.y >= b.x * a.y;
}


bool convex(Punct a, Punct b, Punct c) {
    long double r = a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y);
    return r > 0;
}


void citire(){

    fin >> n;
    for (int i = 0; i < n; i ++)
    {
        fin >> puncte[i].x >> puncte[i].y;
        if ((puncte[i].y < ymin) || (puncte[i].y == ymin && puncte[i].x < xmin))
        {
            ymin = puncte[i].y;
            xmin = puncte[i].x;
            indice_start = i;
        }
    }

    for (int i = 0; i < n; i ++)
    {
        puncte[i].x = puncte[i].x - xmin;
        puncte[i].y = puncte[i].y - ymin;
    }
}


void construieste_Infasuratoare() {

    swap(puncte[0], puncte[indice_start]);
    sort(puncte + 1, puncte + n, comp);

    stiva[top++] = 0;
    stiva[top++] = 1;

    for (int i = 2; i < n; i++)
    {
        while ((top >= 2) && (!convex(puncte[stiva[top - 2]], puncte[stiva[top - 1]], puncte[i]))) {
            top--;
        }
        stiva[top++] = i;
    }
}

void scrie_rez() {
    fout << top << "\n";
    fout << fixed << setprecision(10);
    for (int i = 0; i < top; i ++)
    {
        fout << puncte[stiva[i]].x + xmin << " " << puncte[stiva[i]].y + ymin << "\n";
    }
}

int main() {
    citire();
    construieste_Infasuratoare();
    scrie_rez();
    return 0;
}