Cod sursa(job #1922429)

Utilizator GeoeyMexicanuBadita George GeoeyMexicanu Data 10 martie 2017 17:26:36
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
#include <iostream>
#include <iomanip>
#include <fstream>
#include <algorithm>

using namespace std;

#define x first
#define y second

typedef pair<double , double> Point;

const int max_N=120005;
const double EPS=1e-12;

ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");

int n;
Point v[max_N];
bool viz[max_N];
int st[max_N],head;
void read()
{
    f>>n;
    for(int i=1;i<=n;++i)
        f>>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);
}
void convex_hull()
{
    sort(v+1,v+n+1);
    st[1]=1;st[2]=2;
    head=2;
    viz[2]=true;
    for(int i=1,p=1;i>0;i+=(p=(i==n?-p:p))){
        if(viz[i])
            continue;
        while(head>=2 && cross_product(v[st[head-1]],v[st[head]],v[i])<EPS)
            viz[st[head--]]=false;
        st[++head]=i;
        viz[i]=true;
    }
    g<<head-1<<"\n";
    g<<setprecision(6)<<fixed;
    for(int i=1;i<head;++i)
        g<<v[st[i]].x<<' '<<v[st[i]].y<<"\n";
}
int main()
{
    read();
    convex_hull();
}