Pagini recente » Cod sursa (job #815424) | ape | Rezultatele filtrării | Borderou de evaluare (job #1161903) | Cod sursa (job #2506377)
#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,angle;
} a[120005];
int st[120005];
double Angle[120005];
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 P.angle<Q.angle;
}
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]);
for(int i=2;i<=n;i++){
double x=a[i].x-a[1].x;
double y=a[i].y-a[1].y;
double L=sqrt(x*x+y*y);
a[i].angle=acos(-y/L);
}
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';
}