Pagini recente » Cod sursa (job #2512297) | Cod sursa (job #1261526) | Cod sursa (job #2512143) | Cod sursa (job #1011393) | Cod sursa (job #701139)
Cod sursa(job #701139)
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
int n, pi;
double x[120001], y[120001];
vector<int> puncte;
int stack[120001], stack_size;
inline void stack_push(int x)
{
stack_size++;
stack[stack_size] = x;
}
double arie2(int a, int b, int c)
{
return (double)(x[a] * y[b] + y[a] * x[c] + x[b] * y[c] - y[b] * x[c] - y[a] * x[b] - y[c] * x[a]);
}
bool unghi(int a, int b)
{
return (double)(x[a] - x[pi]) * (y[a] - y[pi]) < (double)(x[b] - x[pi]) * (y[b] - y[pi]);
}
int main()
{
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
scanf("%d", &n);
pi = 0;
x[0] = 1000000001;
y[0] = 1000000001;
for (int i = 1; i <= n; i++)
{
scanf("%lf %lf", &x[i], &y[i]);
if ((x[i] < x[pi]) || ((x[i] == x[pi]) && (y[i] < y[pi])))
pi = i;
}
for (int i = 1; i <= n; i++)
if (i != pi)
puncte.push_back(i);
sort(puncte.begin(), puncte.end(), unghi);
stack_push(pi);
for (int i = 0; i < puncte.size(); i++)
{
if ((stack_size >= 2) && (arie2(stack[stack_size - 1], stack[stack_size], puncte[i]) > 0))
stack_size--;
stack_push(puncte[i]);
}
printf("%d\n", stack_size);
for (int i = 1; i <= stack_size; i++)
printf("%lf %lf\n", x[stack[i]], y[stack[i]]);
}