Cod sursa(job #3245522)

Utilizator Andrei08Petcu Andrei Vlad Andrei08 Data 29 septembrie 2024 12:00:44
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.3 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct punct{
    double x,y;
    int parte;
};
punct v[120003];
int stiva[120003];
bool cmp(punct a,punct b){
    if (b.x!=a.x)
        return (a.x < b.x);
    else
        return (a.y < b.y);
}
double arie(punct a,punct b,punct c){
    return a.x*b.y + b.x*c.y + c.x*a.y - c.x*b.y - a.x*c.y - b.x*a.y;
}
int main(){
    int n,i,k;
    fin>>n;
    for (i=1;i<=n;i++)
        fin>>v[i].x>>v[i].y;
    sort(v+1,v+n+1,cmp);
    for (i=2;i<n;i++){
        if (arie(v[1],v[n],v[i]) < 0)
            v[i].parte=1;
        else
            v[i].parte=2;
    }
    stiva[1]=1;
    k=1;
    for (i=2;i<=n;i++){
        if (v[i].parte!=2){
            while (k>1 && arie(v[stiva[k-1]],v[stiva[k]],v[i]) < 0)
                k--;
            k++;
            stiva[k]=i;
        }
    }
    int cop=k;
    stiva[k]=n;
    for (i=n-1;i>=1;i--){
        if (v[i].parte!=1){
            while (k > cop && arie(v[stiva[k-1]],v[stiva[k]],v[i]) < 0)
                k--;
            k++;
            stiva[k]=i;
        }
    }
    fout<<k-1<<'\n';
    for (i=1;i<=k-1;i++)
        fout<<fixed<<setprecision(6)<<v[stiva[i]].x<<' '<<v[stiva[i]].y<<'\n';
    return 0;
}