Pagini recente » Cod sursa (job #1599717) | Cod sursa (job #572168) | Cod sursa (job #2646643) | Cod sursa (job #1911418) | Cod sursa (job #1374955)
#include <cstdio>
#include <algorithm>
#include <stack>
#define f first
#define s second
using namespace std;
stack <int> st;
pair <double, double> v[120010];
bool frq[120010];
bool det (pair <double, double> a, pair <double, double> b, pair <double, double> c)
{
double d = 1.0 * a.f * b.s + 1.0 * b.f * c.s + 1.0 * a.s * c.f - 1.0 * c.f * b.s - 1.0 * b.f * a.s - 1.0 * c.s * a.f;
return (d < 0.0);
}
int main ()
{
freopen ("infasuratoare.in", "r", stdin);
freopen ("infasuratoare.out", "w", stdout);
int n;
scanf ("%d", &n);
for (int i = 1; i <= n; ++i)
scanf ("%lf %lf", &v[i].f, &v[i].s);
sort (v + 1, v + n + 1);
st.push (1);
st.push (2);
frq[2] = true;
for (int i = 3; i <= n;)
{
int b = st.top ();
st.pop ();
int a = st.top ();
st.push (b);
if (det (v[a], v[b], v[i]))
{
st.push (i);
frq[i++] = true;
}
else frq[b] = false, st.pop ();
}
for (int i = n - 1; i;)
{
if (frq[i])
{
--i;
continue;
}
int b = st.top ();
st.pop ();
int a = st.top ();
st.push (b);
if (det (v[a], v[b], v[i])) st.push (i--);
else st.pop ();
}
st.pop ();
printf ("%d\n", st.size ());
while (!st.empty ())
{
pair <double, double> a = v[st.top ()];
st.pop ();
printf ("%lf %lf\n", a.f, a.s);
}
return 0;
}