Cod sursa(job #1776288)

Utilizator medicinedoctoralexandru medicinedoctor Data 11 octombrie 2016 09:25:54
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.28 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
#define hs h.size()
#define vs v.size()

using namespace std;

struct point {
    double x, y;
};

vector<point> v, h;

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

bool CP(point a, point b)
{
    return (a.x<b.x)||(a.x==b.x)&&(a.y<b.y);
}

bool CA(point a, point b)
{
    return det(v[0], a, b) < 0;
}

void hull()
{
    swap(v[0], *min_element(v.begin(), v.end(), CP));
    sort(v.begin()+1, v.end(), CA);
    h.push_back(v[0]);
    h.push_back(v[1]);
    for (int i = 2; i < vs; i++) {
        while (hs>1 && det(h[hs-2], h[hs-1], v[i])>0)
        {
            h.pop_back();
        }
        h.push_back(v[i]);
    }
    reverse(h.begin(), h.end());
}

void read()
{
    //ifstream cin("infasuratoare.in");
    int n;
    cin>>n;
    v.resize(n);
    for (int i = 0; i < n; i++) {
        cin>>v[i].x>>v[i].y;
    }
}

void write()
{
    //ofstream cout("infasuratoare.out");
    cout<<fixed;
    cout<<hs<<"\n";
    for (int i = 0; i<hs; i++)
    {
        cout<<setprecision(9)<<h[i].x<<" "<<h[i].y<<"\n";
    }
}

int main()
{
    read();
    hull();
    write();
    return 0;
}