Pagini recente » Borderou de evaluare (job #2032062) | Borderou de evaluare (job #225670) | Borderou de evaluare (job #1704744) | Borderou de evaluare (job #1116632) | Cod sursa (job #1980686)
#include <bits/stdc++.h>
#define N 120005
using namespace std;
int n, S[N], u;
const double inf = numeric_limits<double>::max();
struct point {
double x, y;
} p[N];
double det(point p0, point p1, point p2)
{
return ((p1.x - p0.x) * (p2.y - p0.y) - (p2.x - p0.x) * (p1.y - p0.y));
}
double dist(point a, point b)
{
return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}
bool cmp(point a, point b)
{
double d = det(p[1], a, b);
return (d > 0 || (d == 0 && dist(p[1], a) < dist(p[1], b)));
}
void solve()
{
int i;
double d;
u = 0;
S[++u] = 1;
S[++u] = 2;
for (i = 3; i <= n; i++) {
d = det(p[S[u - 1]], p[S[u]], p[i]);
if (d > 0)
S[++u] = i;
else if (d == 0) S[u] = i;
else {
while (d < 0) {
u--;
d = det(p[S[u - 1]], p[S[u]], p[i]);
}
S[++u] = i;
}
}
}
int main()
{
int i;
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
scanf("%i", &n);
int q = 1;
double mx = inf, my = inf;
for (i = 1; i <= n; i++) {
scanf("%lf%lf", &p[i].x, &p[i].y);
if (p[i].y < my || (p[i].y == my && p[i].x < mx)) {
my = p[i].y;
mx = p[i].x;
q = i;
}
}
swap(p[1], p[q]);
sort(p + 2, p + n + 1, cmp);
solve();
printf("%i\n", u);
for (i = 1; i <= u; i++)
printf("%lf %lf\n", p[S[i]].x, p[S[i]].y);
return 0;
}