Pagini recente » Cod sursa (job #1297405) | Cod sursa (job #1651740) | Cod sursa (job #1748045) | Cod sursa (job #3211624) | Cod sursa (job #613372)
Cod sursa(job #613372)
#include <cstdio>
#include <algorithm>
#define N 120005
#define inf 1000000005
using namespace std;
struct punct
{
double x, y, p;
} a[N], s[N], x;
int h, n = 2, poz;
bool cmp(punct a, punct b)
{
if (a.p > b.p)
return false;
return true;
}
void citire()
{
x.x = x.y = inf;
scanf ("%d ", &h);
for (int i = 0; i < h; ++ i)
{
scanf ("%lf %lf ", &a[i].x, &a[i].y);
if (a[i].x < x.x || a[i].x == x.x && a[i].y < x.y)
{
x.x = a[i].x;
x.y = a[i].y;
poz = i;
}
}
a[poz] = a[h - 1];
-- h;
}
void afisare()
{
printf ("%d\n", n);
for (int i = 0; i < n; ++ i)
printf ("%lf %lf\n", s[i].x, s[i].y);
}
void panta()
{
for (int i = 0; i < h; ++ i)
if (a[i].x == x.x)
a[i].p = inf;
else
a[i].p = (a[i].y - x.y) / (a[i].x - x.x);
}
bool determinant(punct a, punct b, punct c)
{
double det = a.x * b.y + a.y * c.x + b.x * c.y - a.y * b.x - b.y * c.x - c.y * a.x;
if (det >= 0)
return true;
return false;
}
void infasuratoare()
{
s[0] = x;
s[1] = a[0];
for (int i = 1; i < h; ++ i)
if (determinant (s[n-2], s[n-1], a[i]))
s[n ++] = a[i];
else
{
while (!determinant (s[n-2], s[n-1], a[i]))
s[-- n] = a[i];
++ n;
}
}
int main()
{
freopen ("infasuratoare.in", "r", stdin);
freopen ("infasuratoare.out", "w", stdout);
citire();
panta();
sort(a, a+h, cmp);
infasuratoare();
afisare();
return 0;
}