Pagini recente » Cod sursa (job #2096248) | Cod sursa (job #2067133) | Cod sursa (job #2859475) | Cod sursa (job #2936278) | Cod sursa (job #2738884)
//#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
struct Point{
double x;
double y;
}v[120005];
double Cross_Product(Point a,Point b,Point c){
return (a.x-b.x)*(a.y-c.y)-(a.y-b.y)*(a.x-c.x);
}
bool mysort(Point a,Point b){
return (Cross_Product(v[1],a,b)>=0);
}
int sta[120005];
int main()
{
int n,poz=1,cnt=0;
double mini;
cin>>n;
for(int i=1;i<=n;i++){
cin>>v[i].x>>v[i].y;
if(v[i].x<v[poz].x){
poz=i;
}
}
swap(v[1],v[poz]);
sta[++cnt]=1;
sort(v+2,v+n+1,mysort);
v[++n]=v[1];
for(int i=2;i<=n;i++){
while(cnt>1){
if(Cross_Product(v[sta[cnt-1]],v[sta[cnt]],v[i])<=0){
cnt--;
}
else
break;
}
sta[++cnt]=i;
}
cout<<cnt-1<<"\n";
for(int i=1;i<cnt;i++){
cout<<v[sta[i]].x<<" "<<v[sta[i]].y<<"\n";
}
return 0;
}