Cod sursa(job #3300597)

Utilizator KapetaneAvram Armand-Florin Kapetane Data 17 iunie 2025 18:26:24
Problema Infasuratoare convexa Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.26 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 && det(stiva[dim-2],stiva[dim-1],pct)<=0)
            pus[stiva[--dim]]=false;
        stiva[dim++]=pct;
        pus[pct]=true;
    }

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