Pagini recente » Cod sursa (job #1463577) | Cod sursa (job #1004248) | Cod sursa (job #2707634) | Cod sursa (job #1934425) | Cod sursa (job #2648556)
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
const int nmax = 120005;
int n;
int st[nmax], vf;
struct pct
{
double x, y;
} x[nmax], stmin;
double panta(const pct& a, const pct& b)
{
return (b.y-a.y)/(b.x-a.x);
}
bool cmp(const pct& x, const pct& y)
{
return (x.y-stmin.y) * (y.x-stmin.x) < (y.y-stmin.y) * (x.x-stmin.x);
}
double det(const pct& a, const pct& b, const pct& c)
{
return a.x * b.y + b.x * c.y + c.x * a.y - a.y * b.x - b.y * c.x - c.y * a.x;
}
int main()
{
f >> n;
for (int i = 1; i <= n; i++)
f >> x[i].x >> x[i].y;
stmin = x[1];
int j = 1;
for (int i = 2; i <= n; i++)
if (x[i].x < stmin.x || (x[i].x == stmin.x && x[i].y < stmin.y))
{
stmin = x[i];
j = i;
}
swap(x[1], x[j]);
sort(x+2, x+n+1, cmp);
vf = 2;
st[1] = 1;
st[2] = 2;
for (int i = 3; i <= n; i++)
{
while (vf >= 2 && det(x[st[vf-1]], x[st[vf]], x[i]) <= 0)
vf--;
vf++;
st[vf] = i;
}
g << vf << '\n';
for (int i = 1; i <= vf; i++)
{
g << fixed << setprecision(6) << x[st[i]].x << ' ' << x[st[i]].y << '\n';
}
return 0;
}