Pagini recente » Cod sursa (job #368229) | Cod sursa (job #1558176) | Cod sursa (job #2156521) | Cod sursa (job #2375828) | Cod sursa (job #2304084)
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
int n,stiva[120001],vf;
struct pct{
double x,y;
}v[120001];
pct rez[120001];
bool cmp(pct a,pct b){
if(a.y == b.y) return a.x < b.x;
return a.y < b.y;
}
bool cmp1(pct a,pct b){
return (a.x > b.x);
}
double triunghi(pct a,pct b,pct c){
return (a.x*(b.y - c.y) + b.x*(c.y - a.y) + c.x*(a.y - b.y));
}
int main()
{
int i;
cin >> n;
for(i = 1;i <= n;i++){
cin >> v[i].x >> v[i].y;
}
sort(v+1,v+n+1,cmp);
stiva[++vf] = 1;
stiva[++vf] = 2;
for(i = 3;i <= n;i++){
while(vf > 1 && triunghi(v[stiva[vf - 1]],v[stiva[vf]],v[i]) < 0)
vf--;
stiva[++vf] = i;
}
int c = 0;
for(i = 1;i <= vf;i++){
rez[++c] = v[stiva[i]];
}
vf = 0;
stiva[++vf] = n;
stiva[++vf] = n-1;
for(i = n - 2;i >= 1;i--){
while(vf > 1 && triunghi(v[stiva[vf - 1]],v[stiva[vf]],v[i]) < 0)
vf--;
stiva[++vf] = i;
}
for(i = 2;i <= vf-1;i++){
rez[++c] = v[stiva[i]];
}
cout << c << "\n";
for(i = 1;i <= c;i++)
cout << fixed << setprecision(6) << rez[i].x << " " << fixed << setprecision(6) <<(double)rez[i].y << "\n";
return 0;
}