Cod sursa(job #1579574)

Utilizator deresurobertoFMI - Deresu Roberto deresuroberto Data 24 ianuarie 2016 21:16:53
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.69 kb
//Deresu Roberto - FMI
//Re :)
#include <iostream>
#include <fstream>
#include <iomanip>
#include <vector>
#include <algorithm>
using namespace std;

struct Point
{
    double x;
    double y;
};

vector<Point> v;
vector<Point> stack;

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

double CrossProduct(Point A, Point B, Point C)
{
    return (B.x - A.x) * (C.y - A.y) - (C.x - A.x) * (B.y - A.y);
}

int Compare(Point P1, Point P2)
{
    return CrossProduct(v[0], P1, P2) > 0;
}

void Read()
{
    Point p;
    int n;

    fin >> n;

    while (fin >> p.x)
    {
        fin >> p.y;

        v.push_back(p);
    }
}

void Sort()
{
    int pos = 0;

    for (int index = 1; index < v.size(); index++)
    {
        if (v[index].x < v[pos].x || (v[index].x == v[pos].x && v[index].y < v[pos].y))
        {
            pos = index;
        }
    }

    swap(v[0], v[pos]);
    sort(v.begin() + 1, v.end(), Compare);
}

void Solve()
{
    Sort();

    stack.push_back(v[0]);
    stack.push_back(v[1]);

    for (int index = 2; index < v.size(); index++)
    {
        while (stack.size() > 1 && CrossProduct(stack[stack.size() - 2], stack[stack.size() - 1], v[index]) < 0)
        {
            stack.pop_back();
        }

        stack.push_back(v[index]);
    }
}

void Print()
{
    fout << stack.size() << "\n";

    fout.setf( std::ios::fixed, std:: ios::floatfield);
    fout.precision(6);

    for (int index = 0; index < stack.size(); index++)
    {
        fout << stack[index].x << " " << stack[index].y << "\n";
    }
}

int main()
{
    Read();

    Solve();

    Print();

    return 0;
}