Pagini recente » Cod sursa (job #2084072) | Cod sursa (job #2632152) | Cod sursa (job #1622915) | Cod sursa (job #2902099) | Cod sursa (job #591164)
Cod sursa(job #591164)
#include <iostream>
#include <vector>
#include <deque>
using namespace std;
#define LD long double
#define PB push_back
#define maxN 120005
#define inf (1 << 30)
double X[maxN], Y[maxN];
vector <int> pct;
deque <int> stiva;
int start;
LD sign (int A, int B, int C)
{
return (LD) 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);
X[0] = inf, 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 (i == start) continue;
pct.PB (i);
}
sort (pct.begin(), pct.end(), cmp);
stiva.PB (start);
for (unsigned int i = 0; i < pct.size(); ++ i)
{
if (pct[i] == start) continue;
for ( ; stiva.size() >= 2 && sign (stiva[stiva.size() - 2], stiva[stiva.size() - 1], pct[i]) > 0; ) stiva.pop_back();
stiva.PB (pct[i]);
}
printf ("%d\n", stiva.size());
for (int i = stiva.size() - 1; i >= 0; -- i) printf ("%lf %lf\n", X[stiva[i]], Y[stiva[i]]);
return 0;
}