Pagini recente » Cod sursa (job #1315798) | Cod sursa (job #2384342) | Cod sursa (job #1491857) | Cod sursa (job #2933591) | Cod sursa (job #1076703)
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
struct punct
{
double x, y;
punct(double x = 0, double y = 0): x(x), y(y)
{
}
}v[120010];
int n;
vector<int> stiva;
int viz[120010];
double dist(punct a, punct b)
{
return sqrt(1.*(a.x-b.x)*(a.x-b.x) + 1.*(a.y-b.y) * (a.y-b.y));
};
double determ(punct a, punct b, punct c)
{
return a.x*(b.y - c.y) + b.x*(c.y-a.y) + c.x*(a.y-b.y);
}
struct cmp
{
bool operator()(punct a, punct b)
{
if(a.y < b.y)
return true;
if(a.y == b.y && a.x < b.x)
return true;
return false;
}
};
void citire()
{
scanf("%d", &n);
float xf, yf;
for(int i = 0; i < n; i++)
{
cin >> v[i].x >> v[i].y;
}
sort(v, v+n, cmp());
}
void adaug(int x)
{
punct a, b, c;
c = v[x];
if(stiva.size() >= 2)
{
a = v[stiva[stiva.size() - 2]];
b = v[stiva[stiva.size() - 1]];
while(determ(a, b, c) <= 0)
{
viz[stiva.back()] = 0;
stiva.pop_back();
if(stiva.size() >= 2)
{
a = v[stiva[stiva.size() - 2]];
b = v[stiva[stiva.size() - 1]];
}
else
break;
}
}
stiva.push_back(x);
viz[x] = 1;
}
void infas()
{
int i;
for(i = 0; i < n; i++)
adaug(i);
for(i--;i >= 0; i--)
if(viz[i] == 0)
adaug(i);
adaug(0);
stiva.pop_back();
}
void afisare()
{
printf("%d\n", stiva.size());
for(int i = 0; i < stiva.size(); i++)
printf("%llf %llf\n", v[stiva[i]].x, v[stiva[i]].y);
}
int main()
{
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
citire();
infas();
afisare();
return 0;
}