Cod sursa(job #2987295)

Utilizator PetruSaveanuSaveanu Petru PetruSaveanu Data 2 martie 2023 10:27:47
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.23 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
struct punct{
double x;
double y;
};
double eps=1e-12;
punct v[120001];
bool cmp(punct a, punct b){
       if(a.x>b.x){
        return 0;
       }
       else if(a.x==b.x){
        if(a.y>b.y)
            return 0;
        else
            return 1;
       }
       else
        return 1;
}
double cross(punct O, punct A, punct B) {
    return (A.x - O.x) * (B.y - O.y) - (B.x - O.x) * (A.y - O.y);
}
int st[120001],head;
bool vis[120001];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>v[i].x>>v[i].y;
    }
    sort(v+1,v+n+1);
    st[1]=1;
    st[2]=2;
    head=2;
    vis[2]=true;

    for (int i = 1, p = 1; i > 0; i += (p = (i == n ? -p : p))) {
        if (vis[i]) continue;
        while (head >= 2 && cross(v[st[head - 1]], v[st[head]], v[i]) < eps)
            vis[st[head--]] = false;
        st[++head] = i;
        vis[i] = true;
    }
        cout << head - 1 << "\n";
    cout << setprecision(6) << fixed;
    for (int i = 1; i < head; ++i)
        cout << v[st[i]].x << " " << v[st[i]].y << "\n";
    return 0;
}