Pagini recente » Cod sursa (job #654619) | Cod sursa (job #576733) | Cod sursa (job #2893464) | Cod sursa (job #2633745) | Cod sursa (job #641679)
Cod sursa(job #641679)
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
#include <cstring>
using namespace std;
const int NMAX = 120000;
const int INF = 0x3f3f3f3f;
double X[NMAX], Y[NMAX];
long double V[NMAX];
int init, ind[NMAX], stack[NMAX], n;
bool comp(int i, int j)
{
return (X[i] - X[init]) * (Y[j] - Y[init]) < (X[j] - X[init]) * (Y[i] * Y[init]);
}
long double cross(int i, int j, int k)
{
return (long double) X[i] * Y[j] - X[j] * Y[i] + X[k] * Y[i] - Y[k] * X[i] + X[j] * Y[k] - X[k] * Y[j];
}
int main()
{
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
scanf("%d", &n);
X[0] = INF, Y[0] = INF;
int init_point = 0;
for (int i = 1; i <= n; ++i) {
scanf("%lf %lf", &X[i], &Y[i]);
if (X[i] < X[init_point] || (X[i] == X[init_point] && Y[i] < Y[init_point]))
init_point = i;
}
init = init_point;
for (int i = 1; i <= n; ++i) {
if (i == init_point)
continue;
ind[++ind[0]] = i;
}
sort(ind + 1, ind + ind[0] + 1, comp);
stack[stack[0] = 1] = init_point;
for (int i = 1; i <= ind[0]; ++i) {
if (ind[i] == init_point)
continue;
while (stack[0] >= 2 && cross(stack[stack[0] - 1], stack[stack[0]], ind[i]) > 0)
--stack[0];
stack[++stack[0]] = ind[i];
}
stack[++stack[0]] = init_point;
printf("%d\n", stack[0] - 1);
reverse(stack + 1, stack + stack[0] + 1);
for (int i = 2; i <= stack[0]; ++i)
printf("%lf %lf\n", X[stack[i]], Y[stack[i]]);
return 0;
}