Cod sursa(job #2544558)

Utilizator CharacterMeCharacter Me CharacterMe Data 12 februarie 2020 11:18:31
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1 kb
#include <bits/stdc++.h>
std::ifstream fin("infasuratoare.in");
std::ofstream fout("infasuratoare.out");
#define x first
#define y second
#define EPSILON 1
typedef std::pair<double, double> pd;
pd list[120005];
int stack[120005];
int head, n;
bool check[120005];
bool verif_conex(pd p1, pd p2, pd p3);
int main()
{
    fin>>n;
    for(int i=1; i<=n; ++i) fin>>list[i].x>>list[i].y;
    std::sort(list+1, list+n+1);
    stack[1]=1; stack[2]=2; check[2]=true; head=2;
    for(int i=1, p=1; i; i+=(p=(i==n?-p:p))){
        if(check[i]) continue;
        while(head>=2 && !verif_conex(list[stack[head-1]], list[stack[head]], list[i])) check[stack[head--]]=false;
        check[i]=true;
        stack[++head]=i;
    }
    fout<<head-1<<"\n";
    fout<<std::fixed<<std::setprecision(8);
    while(--head) fout<<list[stack[head]].first<<" "<<list[stack[head]].second<<"\n";
    return 0;
}
bool verif_conex(pd p1, pd p2, pd p3){
    return (p2.x-p1.x)*(p3.y-p1.y)-(p3.x-p1.x)*(p2.y-p1.y)<EPSILON;
}