Pagini recente » Cod sursa (job #1439917) | Cod sursa (job #1529158) | Cod sursa (job #1986694) | Cod sursa (job #1439971) | Cod sursa (job #1579574)
//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;
}