Cod sursa(job #2531756)

Utilizator BogdanRuleaBogdan Rulea BogdanRulea Data 26 ianuarie 2020 18:16:13
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.08 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
#define NMAX 120005
#define x first
#define y second

using namespace std;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
const double EPS= 1e-12;
typedef  pair <double, double> point;
point v[NMAX];
int n;
void read()
{
    cin>>n;
    for(int i=1; i<=n; i++)
        cin>>v[i].x>>v[i].y;
}
double cross_product(point o,point a,point b)
{
    return (a.x-o.x)*(b.y-o.y)-(b.x-o.x)*(a.y-o.y);
}
bool vis[NMAX];
int st[NMAX],cap;
void convex_hull()
{
    sort(v+1,v+n+1);
    st[1]=1;
    st[2]=2;
    cap=2;
    vis[2]=true;
    for(int i=1,p=1; i>0; i+=(p=(i==n ? -p : p)))
    {

        if(vis[i])
            continue;
        while(cap>=2 && cross_product(v[st[cap-1]],v[st[cap]],v[i])<EPS)
            vis[st[cap--]]=false;
        st[++cap]=i;
        vis[i]=true;
    }
    cout<<cap-1<<'\n';
    cout<<setprecision(6)<<fixed;
   for(int i=1; i<cap; i++)
       cout<<v[st[i]].x<<" "<<v[st[i]].y<<endl;

}
int main()
{
    read();
    convex_hull();
    return 0;
}