Pagini recente » Cod sursa (job #466451) | Cod sursa (job #3283522) | Istoria paginii clasament-arhiva-monthly | Cod sursa (job #469711) | Cod sursa (job #2506373)
#include<fstream>
#include<cmath>
#include<algorithm>
#include<iomanip>
using namespace std;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
int n,tp;
struct punct{
double x,y;
} a[120005];
int st[120005];
double Angle(const punct& P){
double x=P.x-a[1].x;
double y=P.y-a[1].y;
double L=sqrt(x*x+y*y);
return acos(-y/L);
}
int isLeft(const punct &P,const punct &Q,const punct &R){
return ((Q.x-P.x)*(R.y-P.y)-(Q.y-P.y)*(R.x-P.x)>0);
}
int cmp(const punct &P,const punct &Q){
return Angle(P)<Angle(Q);
}
int main(){
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i].x>>a[i].y;
for(int i=2;i<=n;i++)
if(a[1].x>a[i].x ||
a[1].x==a[i].x && a[1].y>a[i].y)
swap(a[1],a[i]);
sort(a+2,a+n+1,cmp);
st[1]=1; st[2]=2;
tp=2;
for(int i=3;i<=n;i++){
while(tp>=2 && !isLeft(a[st[tp-1]],a[st[tp]],a[i])) --tp;
st[++tp]=i;
}
cout<<tp<<'\n';
for(int i=1;i<=tp;i++)
cout<<fixed<<setprecision(6)<<a[st[i]].x<<' '<<a[st[i]].y<<'\n';
}