Pagini recente » Cod sursa (job #1189301) | Cod sursa (job #2587616) | Cod sursa (job #945352)
Cod sursa(job #945352)
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
#define nmax 120010
#define x first
#define y second
#define dd pair<double, double>
dd A[nmax], st[nmax];
int r, N;
struct cmp
{
bool operator () (const dd &A, const dd &B) const
{
if(A.y < B.y) return 1;
if(A.y > B.y) return 0;
if(A.x < B.x) return 1;
return 0;
};
};
int semnDet(dd a, dd b, dd c)
{
double A = a.y - b.y, B = b.x - a.x, C = a.x * b.y - a.y * b.x;
return (A * c.x + B * c.y + C) < 0;
}
void ConvexHull()
{
int i;
st[++r] = A[1];
st[++r] = A[2];
for(i = 3; i <= N; i++)
{
while(r >= 2 && semnDet(st[r - 1], st[r], A[i])) r--;
st[++r] = A[i];
}
for(i = N - 1; i; i--)
{
while(r >= 2 && semnDet(st[r - 1], st[r], A[i])) r--;
st[++r] = A[i];
}
r --;
printf("%i\n", r);
for(i = 1; i <= r; i++) printf("%lf %lf\n", st[i].x, st[i].y);
}
int main()
{
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
int i;
scanf("%i", &N);
for(i = 1; i <= N; i++) scanf("%lf %lf", &A[i].x, &A[i].y);
sort(A + 1, A + N + 1, cmp());
ConvexHull();
return 0;
}