Cod sursa(job #3300599)

Utilizator KapetaneAvram Armand-Florin Kapetane Data 17 iunie 2025 18:33:23
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.4 kb
#include <iostream>
#include <algorithm>
#include <fstream>
#include <iomanip>
#include <cmath>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n;
double x[120005],y[120005];
int stiva[120005],dim;
int pivot;

double distanta(int a, int b)
{
    return (x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b]);
}

int orientare(int p, int q, int r)
{
    double val = (y[q]-y[p])*(x[r]-x[q])-(x[q]-x[p])*(y[r]-y[q]);
    if(abs(val)<1e-12) return 0;
    return (val>0) ? 1 : 2;
}

bool compara(int a, int b)
{
    int o = orientare(pivot, a, b);
    if(o==0) return distanta(pivot, a)<distanta(pivot, b);
    return (o==1);
}

int main()
{
    fin>>n;
    for(int i=1;i<=n;i++)
    fin>>x[i]>>y[i];

    int minim=1;
    for(int i=2;i<=n;i++)
    {
        if(y[i]<y[minim] || (y[i]==y[minim] && x[i]<x[minim]))
            minim=i;
    }

    pivot=minim;
    int ord[120005];
    int cnt=0;
    for(int i=1;i<=n;i++)
        if(i!=pivot) ord[++cnt]=i;

    sort(ord+1,ord+cnt+1,compara);

    stiva[dim++]=pivot;
    stiva[dim++]=ord[1];

    for(int i=2;i<=cnt;i++)
    {
        int pct=ord[i];
        while(dim>=2 && orientare(stiva[dim-2],stiva[dim-1],pct)!=1)
            dim--;
        stiva[dim++]=pct;
    }

    fout<<dim<<endl;
    fout<<setprecision(6)<<fixed;
    for(int i=0;i<dim;i++)
    fout<<x[stiva[i]]<<" "<<y[stiva[i]]<<endl;
    fin.close();
    fout.close();
return 0;
}