Pagini recente » Cod sursa (job #2536231) | Cod sursa (job #171217) | Cod sursa (job #1322744) | Cod sursa (job #2824921) | Cod sursa (job #1922429)
#include <iostream>
#include <iomanip>
#include <fstream>
#include <algorithm>
using namespace std;
#define x first
#define y second
typedef pair<double , double> Point;
const int max_N=120005;
const double EPS=1e-12;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int n;
Point v[max_N];
bool viz[max_N];
int st[max_N],head;
void read()
{
f>>n;
for(int i=1;i<=n;++i)
f>>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);
}
void convex_hull()
{
sort(v+1,v+n+1);
st[1]=1;st[2]=2;
head=2;
viz[2]=true;
for(int i=1,p=1;i>0;i+=(p=(i==n?-p:p))){
if(viz[i])
continue;
while(head>=2 && cross_product(v[st[head-1]],v[st[head]],v[i])<EPS)
viz[st[head--]]=false;
st[++head]=i;
viz[i]=true;
}
g<<head-1<<"\n";
g<<setprecision(6)<<fixed;
for(int i=1;i<head;++i)
g<<v[st[i]].x<<' '<<v[st[i]].y<<"\n";
}
int main()
{
read();
convex_hull();
}