Pagini recente » Cod sursa (job #3362505) | Cod sursa (job #3362506) | Cod sursa (job #3363342) | Cod sursa (job #3362024) | Cod sursa (job #3363694)
#include <bits/stdc++.h>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct per{
double x;
double y;
}a[120005],hull[220005];
bool verif(per a,per b,per c){
double aux=(b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
if(aux<=0){
return false;
}
return true;
}
#define cin f
#define cout g
signed main()
{
int N,i;
cin>>N;
for(i=1;i<=N;i++){
cin>>a[i].x>>a[i].y;
}
sort(a+1,a+1+N,[](per a,per b){
if(a.y!=b.y){
return a.y<b.y;
}
return a.x<b.x;
});
int poz=1;
for(i=1;i<=N;i++){
while(poz>2 && verif(hull[poz-2],hull[poz-1],a[i])==false){
poz--;
}
hull[poz++]=a[i];
}
int lim=poz;
for(i=N-1;i>=1;i--){
while(poz>lim && verif(hull[poz-2],hull[poz-1],a[i])==false){
poz--;
}
hull[poz++]=a[i];
}
cout<<poz-2<<"\n";
for(i=1;i<=poz-2;i++){
cout<<fixed<<setprecision(6)<<hull[i].x<<" "<<hull[i].y<<"\n";
}
return 0;
}