Pagini recente » Cod sursa (job #2486600) | Cod sursa (job #433469) | Cod sursa (job #542741) | Cod sursa (job #2106708) | Cod sursa (job #1344953)
#include <cstdio>
#include <algorithm>
using namespace std;
#define MAXN 120100
struct puncte{double x; double y;};
puncte v[MAXN], ST[MAXN];
int n, vf;
void citire()
{
int i;
scanf("%d", &n);
for(i=1;i<=n;++i)
scanf("%lf%lf", &v[i].x, &v[i].y);
}
inline double cross_product(const puncte& A, const puncte& B, const puncte& C) {
return (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x);
}
inline int cmp(const puncte& p1, const puncte& p2) {
return cross_product(v[1], p1, p2) < 0;
}
void sort_puncte()
{
int pos = 1;
puncte aux;
for (int i = 2; i <= n; ++i)
if (v[i].x < v[pos].x)
pos = i;
aux=v[1];
v[1]=v[pos];
v[pos]=aux;
sort(v + 2, v + n + 1, cmp);
}
void infas()
{
sort_puncte();
ST[1]=v[1];
ST[2]=v[2];
vf=2;
int i;
for(i=3;i<=n;++i)
{
while(vf>=2&&cross_product(ST[vf-1], ST[vf], v[i])>0)
--vf;
ST[++vf]=v[i];
}
}
void afisare()
{
int i;
printf("%d\n", vf);
for(i=vf;i>=1;--i)
printf("%.9f %.9f\n", ST[i].x, ST[i].y);
}
void rezolva_problema()
{
citire();
infas();
afisare();
}
int main()
{
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
rezolva_problema();
return 0;
}