Pagini recente » Cod sursa (job #1061430) | Cod sursa (job #401189) | Cod sursa (job #1179567) | Cod sursa (job #816635) | Cod sursa (job #1796447)
# include <bits/stdc++.h>
# define eps 1e-12
# define point pair < double, double >
# define x first
# define y second
using namespace std;
const int Nmax = 120000 + 5;
vector < point > v;
bool ok[Nmax];
int st[Nmax], n, i, dir, k;
double a, b;
int cmp (double a)
{
if (a + eps > 0) return 1;
if (a + eps < 0) return -1;
return 0;
}
int sgn(point a, point b, point c)
{
double det = a.x * b.y + b.x * c.y + c.x * a.y - b.y * c.x - c.y * a.x - a.y * b.x;
return ( cmp(det) );
}
void solve()
{
ok[2] = true;
st[1] = 1, st[2] = 2;
i = 3, dir = 1, k = 2;
while (!ok[1])
{
while (ok[i])
{
if (i == n) dir *= (-1);
i += dir;
}
while (k >= 2 && sgn(v[st[k - 1]], v[st[k]], v[i]) < 0)
ok[st[k--]] = false;
st[++k] = i;
ok[i] = true;
}
--k;
}
int main ()
{
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
scanf("%d\n", &n);
v.push_back( make_pair(-INT_MAX, -INT_MAX) );
for (i = 1; i <= n; ++i)
{
scanf("%lf %lf\n", &a, &b);
v.push_back( make_pair (a, b) );
}
sort (v.begin(), v.end());
solve();
printf("%d\n", k);
for (i = 1; i <= k; ++i)
printf("%f %f\n", v[st[i]].x, v[st[i]].y);
return 0;
}