Pagini recente » Cod sursa (job #611301) | Cod sursa (job #2442671)
#include <fstream>
#include<algorithm>
#include<iomanip>
using namespace std;
ifstream cin("nim.in");
ofstream cout("nim.out");
#define maxn 100005
#define x first
#define y second
int head=1, N,ans[maxn];
typedef pair<double,double>point;
point v[maxn];
void read(){
cin>>N;
for(int i=1; i<=N; i++)
cin>>v[i].x>>v[i].y;
}
double angle_Check(point A,point B,point C){
return ((B.x-A.x)*(C.y-A.y))-((C.x-A.x)*(B.y-A.y));
}
bool cmp(point A,point B){
return angle_Check(v[1],A,B)<0;
}
void sort_v(){
head=1;
for(int i=2;i<=N;i++)
if(v[head]>v[i])
head=i;
swap(v[head],v[1]);
sort(v+2,v+N+1,cmp);
}
void solve(){
sort_v();
ans[1]=1;
ans[2]=2;
head=2;
for(int i=3; i<=N; i++){
while(head>=2&&angle_Check(v[ans[head-1]],v[ans[head]],v[i])>0)
head--;
ans[++head]=i;
}
cout<<head<<'\n';
for(int i=1; i<=head; i++)
cout<<fixed<<setprecision(9)<<v[ans[i]].x<<' '<<v[ans[i]].y<<'\n';
}
int main()
{
read();
solve();
}