Cod sursa(job #2844293)

Utilizator razvanalexrotaruRazvan Alexandru Rotaru razvanalexrotaru Data 4 februarie 2022 06:55:27
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.2 kb
#include <bits/stdc++.h>
#define x first
#define y second
#define MAX_N 120005
#define cin fin
#define cout fout
using namespace std;
typedef pair<double, double> Point;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");

int n;
Point v[MAX_N];
Point vec[MAX_N];
int head;

void read()
{
    cin>>n;
    for(int i=1;i<=n;++i)
        cin>>v[i].x>>v[i].y;
}

double cross_product(Point A,Point B,Point C)
{
    return(B.x-A.x)*(C.y-A.y)-(B.y-A.y)*(C.x-A.x);
}

bool cmp(Point p1,Point p2)
{
    return cross_product(v[1],p1,p2)<0;
}

void sort_points()
{
    int pos=1;
    for (int i=2;i<=n;++i)
        if (v[i]<v[pos])
            pos=i;
    swap(v[1],v[pos]);
    sort(v+2,v+n+1,cmp);
}

void convex_hull()
{
    sort_points();
    vec[1]=v[1];
    vec[2]=v[2];
    head=2;
    for(int i=3;i<=n;++i)
    {
        while(head>=2 && cross_product(vec[head-1],vec[head],v[i])>0)
            --head;
        vec[++head]=v[i];
    }
}

void write() {
    cout<<fixed;
    cout<<head<<"\n";
    for(int i=head;i>=1;--i)
        cout<<setprecision(9)<<vec[i].x<<" "<<vec[i].y<<'\n';
}

int main() {
    read();
    convex_hull();
    write();
}