Pagini recente » Cod sursa (job #519964) | Cod sursa (job #1761930) | Arhiva de probleme | Cod sursa (job #1282979) | Cod sursa (job #1339744)
#include <cstdio>
#include <algorithm>
#define Nmax (120000 + 10)
#define eps 1e-12
#define punct pair < double , double >
#define X first
#define Y second
using namespace std;
punct p[Nmax];
int S[Nmax];
bool ok[Nmax];
int i , n , h;
int comparare(double A , double B)
{
if (A + eps < B) return -1;
if (B + eps < A) return 1;
return 0;
}
int semn(punct a , punct b , punct c)
{
double A , B , C;
A = a.Y - b.Y;
B = b.X - a.X;
C = a.X * b.Y - b.X * a.Y;
return comparare(A * c.X + B * c.Y + C , 0);
}
void infasuratoare()
{
int k = 0 , mod = 1 , i = 3;
sort(p + 1, p + n + 1);
S[++k] = 1; S[++k] = 2; ok[2] = true;
while (!ok[1])
{
while (ok[i])
{
if (i == n) mod *= -1;
i += mod;
}
while (k >= 2 && semn(p[S[k-1]] , p[S[k]] , p[i]) == -1)
ok[ S[k--] ] = false;
S[++k] = i; ok[i] = true;
}
h = k - 1;
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d", &n);
for (i = 1; i <= n; ++i)
scanf("%lf %lf", &p[i].X , &p[i].Y);
infasuratoare();
printf("%d\n", h);
for (i = 2; i <= h + 1; ++i)
printf("%lf %lf\n", p[S[i]].X , p[S[i]].Y);
return 0;
}