Cod sursa(job #1529058)

Utilizator kiunyAndrei Gavrila kiuny Data 20 noiembrie 2015 14:48:13
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include <iostream>
#include <vector>
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;

ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");

struct point
{
    double x, y;
    bool operator<(const point &p) const
    {
        return x < p.x || (x == p.x && y < p.y);
    }

};

double dot(point o, point a, point b)
{
    return (double) (a.x - o.x) * (b.y - o.y) - (double)(a.y - o.y)*(b.x-o.x);
}

vector <point> v, h;
int n;
point p;

int main()
{
    int k = 0;
    fin >> n;
    for(int i = 0; i < n; i++)
    {
        fin >> p.x >> p.y;
        v.push_back(p);
    }

    sort(v.begin(), v.end());
    h.resize(2*n);
    for(int i = 0; i < n; i++)
    {
        while(k >= 2 && dot(h[k-2], h[k-1], v[i]) <= 0) k--;
        h[k++] = v[i];
    }

    for(int i = n-2, t = k+1; i >= 0; i--)
    {
        while( k >= t && dot(h[k-2], h[k-1], v[i]) <= 0) k--;
        h[k++] = v[i];
    }
    h.resize(k);
    fout << h.size()-1 << '\n';
    for(int i = 0; i < h.size()-1; i++)
    {
        fout <<fixed << setprecision(6) << h[i].x << " " << h[i].y << '\n';
    }
    return 0;
}