Cod sursa(job #2558137)

Utilizator rd211Dinucu David rd211 Data 26 februarie 2020 12:30:01
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.12 kb
#include <bits/stdc++.h>

using namespace std;
const int NMAX = 120005;
const double eps = 1e-12;
int n;
pair<double,double> points[NMAX];
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int stac[NMAX];
int head = 0;

double crossProd(pair<double,double> a,pair<double,double>b,pair<double,double> o)
{
    return (a.first-o.first)*(b.second-o.second)-
           (b.first-o.first)*(a.second-o.second);
}
bool viz[NMAX];
void hull()
{
    sort(points+1,points+n+1);
    stac[1]=1;
    stac[2]=2;
    head =2;
    viz[2]=true;
    for(int i = 1,p=1;i>0;i+=(p= ((i==n)?(-p):(p))))
    {
        if(viz[i])continue;
        while(head>=2 && crossProd(points[stac[head]],points[stac[head-1]],points[i])<=eps)
        {
            viz[stac[head--]]=false;
        }
        stac[++head]=i;
        viz[i]=true;
    }
}
int main()
{
    fin>>n;
    for(int i = 1;i<=n;i++) fin>>points[i].first>>points[i].second;

    hull();
    fout<<head-1<<'\n';
    for(int i = head-1;i>=1;i--) fout<<fixed<<setprecision(6)<<points[stac[i]].first<<" "<<points[stac[i]].second<<'\n';
    return 0;
}