Pagini recente » Cod sursa (job #525235) | Cod sursa (job #1975717) | Cod sursa (job #1391998) | Cod sursa (job #684280) | Cod sursa (job #704147)
Cod sursa(job #704147)
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
#define maxN 120010
#define PB push_back
#define LD long double
#define inf (1 << 30)
double X[maxN], Y[maxN];
vector <int> P, st;
vector <int> :: iterator it;
int start;
long double sign (int A, int B, int C)
{
return (long double) X[A] * Y[B] + X[B] * Y[C] + X[C] * Y[A] - Y[A] * X[B] - Y[B] * X[C] - Y[C] * X[A];
}
inline int cmp (int A, int B)
{
LD x1 = X[A], y1 = Y[A];
LD x2 = X[B], y2 = Y[B];
return (double) (x1 - X[start]) * (y2 - Y[start]) < (double) (y1 - Y[start]) * (x2 - X[start]);
}
int main()
{
freopen ("infasuratoare.in", "r", stdin);
freopen ("infasuratoare.out", "w", stdout);
int N;
scanf ("%d", &N);
start = 0;
X[0] = Y[0] = inf;
for (int i = 1; i <= N; ++ i)
{
scanf ("%lf %lf", &X[i], &Y[i]);
if (X[i] == X[start] && Y[i] < Y[start]) start = i;
if (X[i] < X[start]) start = i;
}
for (int i = 1; i <= N; ++ i)
{
if (start == i) continue;
P.PB (i);
}
sort (P.begin(), P.end(), cmp);
st.PB (start);
for (unsigned i = 0; i < P.size(); ++ i)
{
while (st.size() >= 2)
{
int sz = st.size();
if (sign (st[sz - 2], st[sz - 1], P[i]) <= 0) break;
st.pop_back();
}
st.PB (P[i]);
}
printf ("%d\n", st.size());
for (it = st.end() - 1; it != st.begin() - 1; -- it) printf ("%lf %lf\n", X[*it], Y[*it]);
return 0;
}