Pagini recente » Cod sursa (job #340129) | Cod sursa (job #2038972) | Cod sursa (job #1732917) | Cod sursa (job #984083) | Cod sursa (job #1899455)
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
int n, f[120005];
struct punct{
double x, y;
}p[120005];
vector <int> stiva;
inline bool cmp(punct x, punct y){
if(x.x != y.x) return x.x < y.x;
return x.y < y.y;
}
inline double Arie(punct a, punct b, punct c){
return (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y);
}
int main()
{
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
scanf("%d", &n);
for(int i = 1; i <= n ; ++i)
scanf("%lf%lf", &p[i].x, &p[i].y);
sort(p + 1, p + n + 1, cmp);
stiva.push_back(1);
stiva.push_back(2);
f[2] = 1;
for(int i = 1; i <= n ; ++i){
while(stiva.size() > 1 && Arie(p[stiva[stiva.size() - 2]], p[stiva[stiva.size() - 1]], p[i]) <= 0)
f[stiva[stiva.size() - 1]] = 0,stiva.pop_back();
stiva.push_back(i);
f[i] = 1;
}
for(int i = n; i >= 1 ; --i){
if(f[i] == 1) continue ;
while(stiva.size() > 1 && Arie(p[stiva[stiva.size() - 2]], p[stiva[stiva.size() - 1]], p[i]) <= 0)
f[stiva[stiva.size() - 1]] = 0,stiva.pop_back();
stiva.push_back(i);
f[i] = 1;
}
printf("%d\n", stiva.size() - 1);
for(int i = 1; i < stiva.size() ; ++i)
printf("%f %f\n", p[stiva[i]].x, p[stiva[i]].y);
return 0;
}