Pagini recente » Cod sursa (job #827558) | Cod sursa (job #2362961) | Cod sursa (job #800249) | Cod sursa (job #3219062) | Cod sursa (job #885455)
Cod sursa(job #885455)
#include <cstdio>
#include <algorithm>
#include <cmath>
#define max_N 120004
#define dd pair <double,double>
#define x first
#define y second
using namespace std;
const char iname[] = "infasuratoare.in";
const char oname[] = "infasuratoare.out";
int N, i, j, head, pos;
dd v[max_N], stiva[max_N];
inline double detSemn(const dd &A, const dd &B, const dd &C)
{
double p1 = A.x * (-1); double p2 = A.y * (-1);
double a = p1 + B.x; double b = p2 + B.y;
double c = p1 + C.x; double d = p2 + C.y;
return (a * d - (b * c));
}
struct cmp
{
bool operator() (const dd &pc1, const dd &pc2) const
{
if (detSemn(v[1], pc1, pc2) < 0) return 1;
return 0;
};
};
int main()
{
freopen(iname,"r",stdin);
freopen(oname,"w",stdout);
scanf ("%d", &N);
for (i = 1; i <= N; ++i)
scanf("%lf%lf", &v[i].x, &v[i].y);
pos = 1;
for (i = 2; i <= N; ++i)
if (v[i] < v[pos])
pos = i;
swap(v[1], v[pos]);
sort(v + 2, v + N + 1, cmp());
stiva[1] = v[1];
stiva[2] = v[2];
head = 2;
for (i = 3; i <= N; ++i)
{
while (head >= 2 && detSemn(stiva[head - 1], stiva[head], v[i]) > 0)
--head;
stiva[++head] = v[i];
}
printf("%d\n", head);
for (i = head; i >= 1; --i)
{
printf ("%lf %lf", stiva[i].x, stiva[i].y);
printf ("\n");
}
return 0;
}