Pagini recente » Cod sursa (job #661624) | Cod sursa (job #2913478) | Cod sursa (job #1194420) | Cod sursa (job #831396) | Cod sursa (job #1610154)
#include <fstream>
#include <iomanip>
#include <algorithm>
using namespace std;
ifstream f ("infasuratoare.in");
ofstream g ("infasuratoare.out");
int n;
struct point
{
double x;
double y;
} v[120005], stiva[120005];
double slope (point a, point b, point c)
{
return (b.y - a.y) * (c.x - a.x) - (b.x - a.x) * (c.y - a.y);
}
bool slope_compare (const point& a, const point& b)
{
return (slope (v[1], a, b) < 0);
}
void read ()
{
f >> n;
for (int i = 1; i <= n; i ++)
f >> v[i].x >> v[i].y;
}
void sort_the_points ()
{
int poz = 1;
for (int i = 2; i <= n; i ++)
if (v[i].y < v[poz].y || (v[i].y == v[poz].y && v[i].x < v[poz].x))
poz = i;
point aux;
aux = v[1];
v[1] = v[poz];
v[poz] = aux;
sort (v + 2, v + n + 1, slope_compare);
}
void convex_hull ()
{
sort_the_points ();
stiva[1] = v[1];
stiva[2] = v[2];
int last = 2;
for (int i = 3; i <= n; i ++)
{
while(slope (stiva[last - 1], stiva[last], v[i]) > 0 && last >= 2)
-- last;
stiva[++ last] = v[i];
}
g << last << '\n';
g << fixed << setprecision (6);
for (int i = 1; i <= last; i ++)
g << stiva[i].x << " " << stiva[i].y << '\n';
}
int main()
{
read ();
convex_hull ();
f.close ();
g.close ();
return 0;
}