Cod sursa(job #3362506)

Utilizator Robert_Tucker_GBRobert Mihai Tucker Robert_Tucker_GB Data 10 august 2026 11:30:10
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.5 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>

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

const int Nmax=120000;
const double inf=1e9+5;

int n;
int sol[Nmax];

struct punct{
    double x, y;
}v[Nmax];

// = 0 -> coliniare
// < 0 -> C este la dreapta lui AB
// > 0 -> C este la stanga lui AB
double det(punct a, punct b, punct c){
    return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}

bool cmp(punct a, punct b){
    return det(a, b, v[0])>0;
}

int main(){
    fin>>n;

    // cautam punctul cel mai de jos
    int ind=0;
    for (int i=0; i<n; i++){
        fin>>v[i].x>>v[i].y;

        if (v[i].y<v[ind].y)
            ind=i;
        else if (v[i].y==v[ind].y && v[i].x<v[ind].x)
            ind=i;
    }
    // ind reprezinta indicele punctului cautat
    swap(v[0], v[ind]); // punctul "ind" devine primul

    // sortam punctele dupa unghi in jurul lui v[0]
    sort(v+1, v+n, cmp);

    // Convex Hull cu Graham Scan
    int nrp=0;
    sol[0]=0; nrp++;
    sol[1]=1; nrp++;
    for (int i=2; i<n; i++){
        // scoatem toate punctele neconforme din infasuratoare
        while (det(v[sol[nrp-2]], v[sol[nrp-1]], v[i])<0)
            nrp--;

        // adaugam punctul curent la infasuratoare
        sol[nrp]=i; nrp++;
    }

    fout<<nrp<<'\n';
    for (int i=0; i<nrp; i++)
        fout<<fixed<<setprecision(12)<<v[sol[i]].x<<' '<<v[sol[i]].y<<'\n';

    return 0;
}