Pagini recente » Cod sursa (job #2080804) | Cod sursa (job #2393070) | Cod sursa (job #2264832) | Cod sursa (job #1857533) | Cod sursa (job #1645767)
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <stack>
#define Point pair<double,double>
#define x first
#define y second
#define N 120005
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
Point v[N],stac[N];
int head,n;
void read()
{
fin>>n;
for(int i=1;i<=n;i++) fin>>v[i].x>>v[i].y;
}
inline double produs_incrucisat(const Point & A,const Point& B,const Point& C)
{
return (B.x-A.x)*(C.y-A.y)-(B.y-A.y)*(C.x-A.x);
}
inline int cmp(const Point& p1,const Point& p2)
{
return produs_incrucisat(v[1],p1,p2)<0;
}
void sort_points()
{
int pos=1;
for(int i=1;i<=n;i++) if(v[i]<v[pos]) pos=i;
swap(v[1],v[pos]);
sort(v+2,v+n+1,cmp);
}
void convex_hull()
{
sort_points();
stac[1]=v[1];
stac[2]=v[2];
head=2;
for(int i=3;i<=n;i++)
{
while(head>=2 && produs_incrucisat(stac[head-1],stac[head],v[i])>0) --head;
stac[++head]=v[i];
}
}
void write()
{
fout<<fixed;
fout<<head<<"\n";
for(int i=head;i>=1;i--)
{
fout<<setprecision(9)<<stac[i].x<<" "<<stac[i].y<<"\n";
}
}
int main()
{
read();
convex_hull();
write();
}