Pagini recente » Cod sursa (job #2496278) | Cod sursa (job #120968) | Cod sursa (job #1576868) | Cod sursa (job #2484585) | Cod sursa (job #2531756)
#include <fstream>
#include <algorithm>
#include <iomanip>
#define NMAX 120005
#define x first
#define y second
using namespace std;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
const double EPS= 1e-12;
typedef pair <double, double> point;
point v[NMAX];
int n;
void read()
{
cin>>n;
for(int i=1; i<=n; i++)
cin>>v[i].x>>v[i].y;
}
double cross_product(point o,point a,point b)
{
return (a.x-o.x)*(b.y-o.y)-(b.x-o.x)*(a.y-o.y);
}
bool vis[NMAX];
int st[NMAX],cap;
void convex_hull()
{
sort(v+1,v+n+1);
st[1]=1;
st[2]=2;
cap=2;
vis[2]=true;
for(int i=1,p=1; i>0; i+=(p=(i==n ? -p : p)))
{
if(vis[i])
continue;
while(cap>=2 && cross_product(v[st[cap-1]],v[st[cap]],v[i])<EPS)
vis[st[cap--]]=false;
st[++cap]=i;
vis[i]=true;
}
cout<<cap-1<<'\n';
cout<<setprecision(6)<<fixed;
for(int i=1; i<cap; i++)
cout<<v[st[i]].x<<" "<<v[st[i]].y<<endl;
}
int main()
{
read();
convex_hull();
return 0;
}