Pagini recente » Rezultatele filtrării | Cod sursa (job #1985396)
#include <bits/stdc++.h>
#define N 120001
using namespace std;
int n, m, s[N], t;
double inf = 1000000005;
struct punct { double x, y; } p[N];
double det(punct p0, punct p1, punct p2)
{
return (p1.x - p0.x) * (p2.y - p0.y) - (p1.y - p0.y) * (p2.x - p0.x);
}
double dist(punct p1, punct p2)
{
return (p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y);
}
bool cmp(punct a, punct b)
{
double d = det(p[1], a, b);
return d > 0 || (d == 0 && dist(a, p[1]) < dist(b, p[1]));
}
void solve()
{
int i;
double d;
t = 2;
s[1] = 1; s[2] = 2;
for (i = 3; i <= n; i++)
{
d = det(p[s[t-1]], p[s[t]], p[i]);
if (d > 0)
s[++t] = i;
else if (d == 0)
s[t] = i;
else
{
while (det(p[s[t-1]], p[s[t]], p[i]) < 0)
t--;
s[++t] = i;
}
}
}
int main()
{
freopen ("infasuratoare.in","r",stdin);
freopen ("infasuratoare.out","w",stdout);
scanf("%i", &n);
double mx = inf, my = inf;
int q, i;
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", t);
for (i = 1; i <= t; i++)
printf("%lf %lf\n", p[s[i]].x, p[s[i]].y);
return 0;
}