Pagini recente » oni_2006_10_z1 | Cod sursa (job #114305) | Cod sursa (job #1467338) | Cod sursa (job #714689) | Cod sursa (job #3122861)
#include <iostream>
#include <fstream>
#include <deque>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <string>
using namespace std;
typedef unsigned int uint;
const string task = "infasuratoare";
class Point
{
public:
double x;
double y;
Point(double _x = 0, double _y = 0)
{
this->x = _x;
this->y = _y;
}
};
namespace utils
{
char orientation(Point a, Point b, Point c)
{
double delta = (b.y - a.y) * (c.x - b.x) - (b.x - a.x) * (c.y - b.y);
if(delta == 0)
{
return '*';
}
else if(delta > 0)
{
return '+';
}
else
{
return '-';
}
}
uint begin(deque<Point> point_set)
{
uint best_index = 0, size = point_set.size();
for(int index = 1; index < size; index++)
{
if(point_set[index].x < point_set[best_index].x)
{
best_index = index;
}
}
return best_index;
}
}
deque<Point> hull(deque<Point> point_set)
{
deque<Point> Hull = {};
uint size = point_set.size();
if(size != 0 && size != 1 && size != 2)
{
uint begin_index = utils::begin(point_set), current_index = begin_index;
do
{
Hull.push_back(point_set[current_index]);
uint best_index = (current_index + 1) % size;
for(uint index = 0; index < size; index++)
{
if(utils::orientation(point_set[current_index], point_set[index], point_set[best_index]) == '-')
{
best_index = index;
}
}
current_index = best_index;
}
while(current_index != begin_index);
}
return Hull;
}
int main()
{
uint size;
double x, y;
deque<Point> point_set, Hull;
ifstream fin(task + ".in");
ofstream fout(task + ".out");
fin >> size;
while(fin >> x >> y)
{
point_set.push_back(Point(x, y));
}
Hull = hull(point_set);
sort(Hull.begin(), Hull.end(),
[] (const Point& a, const Point& b) -> bool
{
return atan2(a.y, a.x) < atan2(b.y, b.x);
}
);
fout << Hull.size() << '\n';
for(auto point : Hull)
{
fout << setprecision(12) << point.x << ' ' << point.y << '\n';
}
return 0;
}