Pagini recente » Statistici Rares.Dumitru (FloppyBestial) | Cod sursa (job #2686076) | Cod sursa (job #974795) | Istoria paginii utilizator/adasoare | Cod sursa (job #2442740)
#include <fstream>
#include<algorithm>
#include<vector>
#include<iomanip>
using namespace std;
ifstream cin("nim.in");
ofstream cout("nim.out");
#define maxn 130005
#define x first
#define y second
int head=1, N;
typedef pair<double,double>point;
point v[maxn],ans[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]=v[1];
ans[2]=v[2];
head=2;
for(int i=3; i<=N; i++){
while(head>=2&&angle_Check(ans[head-1],ans[head],v[i])>0)
head--;
ans[++head]=v[i];
}
cout<<head<<'\n';
for(int i=1; i<=head; i++)
cout<<fixed<<setprecision(9)<<ans[i].x<<' '<<ans[i].y<<'\n';
}
int main()
{
read();
solve();
}