Pagini recente » Cod sursa (job #1914700) | Cod sursa (job #2516289) | Cod sursa (job #2545798) | Cod sursa (job #1379296) | Cod sursa (job #2384854)
#include <bits/stdc++.h>
using namespace std;
const int N = 120000;
struct coord{double x, y;}v[N], dr[N], st[N], s1[N], s2[N];
bool cmp(coord a, coord b)
{
if (a.y < b.y)
return true;
else if (b.x < b.x)
return true;
else
return false;
}
double arie(coord a, coord b, coord c)
{
return a.x * b.y + b.x * c.y + a.y * c.x
- b.y * c.x - c.y * a.x - b.x * a.y;
}
coord atribuire(double &a, double &b)
{
coord nr;
nr.x = a;
nr.y = b;
return nr;
}
int main()
{
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
int n, i;
scanf("%d", &n);
for (i = 1; i <= n; i++)
scanf("%lf%lf", &v[i].x, &v[i].y);
sort(v + 1, v + n + 1, cmp);
int k = 0, l = 0, A;
dr[++k] = st[++l] = v[1];
for (i = 2; i < n; i++)
{
coord a, b, c;
a = atribuire(v[1].x, v[1].y);
b = atribuire(v[n].x, v[n].y);
c = atribuire(v[i].x, v[i].y);
A = arie(a, b, c);
if (A < 0)
dr[++k] = c;
else if (A > 0)
st[++l] = c;
}
dr[++k] = st[++l] = v[n];
//pe dreapta
int m = 3;
s1[1] = dr[1];
s1[2] = dr[2];
if (k >= 3)
{
s1[3] = dr[3];
for (i = 4; i <= k; i++)
if (arie(s1[m - 1], s1[m], dr[i]) > 0)
s1[++m] = dr[i];
else
s1[m] = dr[i];
}
//pe stanga
int w = 3;
s2[1] = st[1];
s2[2] = st[2];
if (l >= 3)
{
s2[3] = st[3];
for (i = 4; i <= l; i++)
if (arie(s2[w - 1], s2[w], st[i]) < 0)
s2[++w] = st[i];
else
s2[w] = st[i];
}
printf("%d\n", w + m - 2);
for (i = 1; i <= m; i++)
printf("%.12lf %.12lf\n", s1[i].x, s1[i].y);
for (i = w - 1; i > 1; i--)
printf("%.12lf %.12lf\n", s2[i].x, s2[i].y);
return 0;
}