Cod sursa(job #1922607)

Utilizator VictoriaNevTascau Victoria VictoriaNev Data 10 martie 2017 18:02:30
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
#include <fstream>
#include <iomanip>
#include <algorithm>
#define x first
#define y second
using namespace std;
const int NMAX=120001;
typedef pair<double, double> point;
point v[NMAX], st[NMAX];
int n;


inline double cp(const point &a, const point &b, const point &c)
{
    return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}


inline int cmp(const point &a, const point &b)
{
    return cp(v[1], a, b)<0;
}


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


int main()
{
    ifstream in("infasuratoare.in");
    ofstream out("infasuratoare.out");
    in>>n;
    for(int i=1; i<=n; i++)
        in>>v[i].x>>v[i].y;
    sorting();
    st[1]=v[1];
    st[2]=v[2];
    int top=2;
    for(int i=3; i<=n; i++)
    {
        while(top>=2 && cp(st[top-1], st[top], v[i])>0)
            top--;
        st[++top]=v[i];
    }
    out<<top<<'\n';
    for(int i=top; i>=1; i--)
        out<<setprecision(8)<<fixed<<st[i].x<<' '<<st[i].y<<'\n';
    return 0;
}