Cod sursa(job #1952614)

Utilizator marcudaniel12Marcu Tudor Daniel marcudaniel12 Data 4 aprilie 2017 11:32:36
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
#include <fstream>
#include <algorithm>
#include <cmath>
#include <iomanip>
#define NMAX 121002
using namespace std;

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

struct punct {
    double x,y;
    } v[NMAX], st[NMAX];

double det(punct a, punct b, punct c)
{
    return a.x * b.y + b.x * c.y + c.x * a.y - c.x * b.y - b.x * a.y - a.x * c.y;
}

bool cr1(punct a, punct b){
    if ( a.x == b.x )
        return a.y < b.y;
    return a.x < b.x;
}

bool cr2(punct a, punct b){
    return det (v[1], a, b) < 0;
}

int n,k;

int main(){
    f >> n;
    for (int i = 1; i <= n; i++)
        f >> v[i].x >> v[i].y;
    sort(v+1,v+n+1,cr1);
    sort(v+2,v+n+1,cr2);
    st[1]=v[1];
    st[2]=v[2];
    st[3]=v[3];
    k=3;
    for (int i=4; i<=n; ++i){
        while ((k >= 3) && (det(st[k],st[k-1],v[i])<0))
            k--;
        st[++k]=v[i];
    }
    g<<k<<'\n';
    g<<fixed<<setprecision(12);
    for (int i=k; i>=1; i--)
        g<<st[i].x<<" "<<st[i].y<<'\n';
    return 0;
}