Pagini recente » Cod sursa (job #2852694) | Cod sursa (job #3040937) | Cod sursa (job #2889856) | Cod sursa (job #2765083) | Cod sursa (job #2510229)
#include <bits/stdc++.h>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
const int nmax = 120005;
bool fv[nmax];
int down[nmax];
int up[nmax];
struct coord
{
double x, y;
}punct[nmax];
double det(coord a, coord b, coord c)
{
return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}
int main()
{
int n;
f >> n;
for (int i = 1; i <= n; ++ i)
{
double x, y;
f >> x >> y;
punct[i] = {x, y};
}
sort(punct + 1, punct + 1 + n, [](const coord a, const coord b) -> bool{
if (a.x == b.x)
return a.y < b.y;
return a.x < b.x;
});
int lvl1 = 0;
for (int i = 1; i <= n; ++ i)
{
while (lvl1 >= 2 && det(punct[i], punct[down[lvl1 - 1]], punct[down[lvl1]]) > 0)
fv[down[lvl1 --]] = false;
down[++ lvl1] = i;
fv[i] = true;
}
fv[1] = fv[n] = false;
int lvl2 = 0;
for (int i = n; i >= 1; -- i)
{
if (fv[i])
continue;
while (lvl2 >= 2 && det(punct[i], punct[up[lvl2 - 1]], punct[up[lvl2]]) > 0)
lvl2 --;
up[++ lvl2] = i;
}
g << lvl1 + lvl2 - 2 << '\n';
for (int i = lvl1 - 1; i > 1; -- i)
g << fixed << setprecision(12) << punct[down[i]].x << " " << punct[down[i]].y << '\n';
for (int i = lvl2; i >= 1; -- i)
g << fixed << setprecision(12) << punct[up[i]].x << " " << punct[up[i]].y << '\n';
}