Cod sursa(job #3300598)

Utilizator KapetaneAvram Armand-Florin Kapetane Data 17 iunie 2025 18:31:26
Problema Infasuratoare convexa Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.29 kb
#include <iostream>
#include <algorithm>
#include <fstream>
#include <iomanip>
using namespace std;

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

int n;
double x[120005],y[120005];
int stiva[120005],dim;
bool pus[120005];
bool compara(int a,int b)
{
 if(x[a]!=x[b]) return x[a]<x[b];
 return y[a]<y[b];
}
double det(int a,int b,int c)
{
 return (x[b]-x[a])*(y[c]-y[a])-(x[c]-x[a])*(y[b]-y[a]);
}
int main()
{
    fin>>n;
    for(int i=1;i<=n;i++) fin>>x[i]>>y[i];

    int ord[120005];
    for(int i=1;i<=n;i++)  ord[i]=i;

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

    for(int i=1;i<=n;i++)
    {
        int pct=ord[i];
        while(dim>=2&&det(stiva[dim-2],stiva[dim-1],pct)<=0)
        pus[stiva[--dim]]=false;
    stiva[dim++]=pct;
    pus[pct]=true;
    }

    int start=dim;
    for(int i=n-1;i>=1;i--)
    {
        int pct=ord[i];
        if(pus[pct]) continue;
        while(dim>=start+1&&det(stiva[dim-2],stiva[dim-1],pct)<=0)
            pus[stiva[--dim]]=false;

        stiva[dim++]=pct;
        pus[pct]=true;
    }
    if(dim>=2&&x[stiva[0]]==x[stiva[dim-1]]&&y[stiva[0]]==y[stiva[dim-1]])
            dim--;

    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;
}