Pagini recente » Cod sursa (job #866395) | Cod sursa (job #2399219) | Cod sursa (job #3273289) | Cod sursa (job #2444334) | Cod sursa (job #803919)
Cod sursa(job #803919)
#include <cstdio>
#include <algorithm>
using namespace std;
struct Punct{
double x;
double y;
}p[120002];
Punct q[120002];
bool dupa_x(Punct a, Punct b)
{
if(a.x < b.x || (a.x == b.x && a.y < b.y))
return 1;
return 0;
}
int intoarce(Punct a , Punct b, Punct c)
{
if((b.x * c.y + a.x * b.y + c.x * a.y - a.y * b.x - c.x * b.y - a.x * c.y) >= 0)
return 1;
else
return 0;
}
int n;
int main()
{
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
scanf("%d",&n);
for(int i = 1; i <= n; i++)
{
scanf("%lf%lf", &p[i].x, &p[i].y);
}
sort(p + 1, p + n + 1, dupa_x);
q[1].x = p[1].x;
q[1].y = p[1].y;
int h = 1;
for(int i = 2; i <= n; i++)
{
while(h > 1 && !intoarce(q[h - 1], q[h], p[i]))
h = h - 1;
h = h + 1;
q[h].x = p[i].x;
q[h].y = p[i].y;
}
for(int i = n - 1; i >= 1; i--)
{
while(!intoarce(q[h - 1], q[h], p[i]))
h = h - 1;
h = h + 1;
q[h].x = p[i].x;
q[h].y = p[i].y;
}
h = h - 1;
printf("%d\n", h);
for(int i = 1; i <= h ; i++)
{
printf("%.6lf %.6lf\n", q[i].x, q[i].y);
}
return 0;
}