Cod sursa(job #1539605)

Utilizator deresurobertoFMI - Deresu Roberto deresuroberto Data 1 decembrie 2015 01:31:32
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.71 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;
}