Cod sursa(job #3226600)

Utilizator AndreiBOTOBotocan Andrei AndreiBOTO Data 22 aprilie 2024 10:48:45
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.48 kb
#include <bits/stdc++.h>

#pragma optimize GCC ("Ofast")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

///#include <tryhardmode>
///#include <GODMODE::ON>

using namespace std;

#define cin fin
#define cout fout

ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");

const int NMAX=12e4+5;

struct coords{
    long double x;
    long double y;
}v[NMAX];

vector<coords>hull;

long double area(coords a,coords b,coords c)
{
    return (b.y-a.y)*(c.x-b.x)-(b.x-a.x)*(c.y-b.y);
}

bool cmp(coords a,coords b)
{
    if(area(v[1],a,b)>=0)
        return false;
    return true;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n,i,j,ind=1;
    cin>>n;
    for(i=1;i<=n;i++)
        cin>>v[i].x>>v[i].y;
    for(i=2;i<=n;i++)
    {
        if(v[ind].y>=v[i].y)
        {
            if(v[ind].y>v[i].y)
                ind=i;
            else
            {
                if(v[ind].x<v[i].x)
                    ind=i;
            }
        }
    }
    swap(v[1],v[ind]);
    sort(v+2,v+n+1,cmp);
    hull.push_back(v[1]);
    hull.push_back(v[2]);
    for(i=3;i<=n;i++)
    {
        while(hull.size()>=2 && area(hull[hull.size()-2],hull[hull.size()-1],v[i])>=0)
            hull.pop_back();
        hull.push_back(v[i]);
    }
    cout<<hull.size()<<"\n";
    for(auto i:hull)
        cout<<fixed<<setprecision(12)<<i.x<<" "<<i.y<<"\n";
    return 0;
}