Pagini recente » Cod sursa (job #1812500) | Cod sursa (job #1391594) | Cod sursa (job #2438489) | Cod sursa (job #1586290) | Cod sursa (job #1678370)
#include <iostream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#define mp make_pair
#define x first
#define y second
#define MAXN 120001
#define INFILE "infasuratoare.in"
#define OUTFILE "infasuratoare.out"
using namespace std;
ifstream f(INFILE);
ofstream g(OUTFILE);
int n,i,pos,head;
double a,b;
pair<double,double> v[MAXN],s[MAXN];
inline double cross_prod(const pair<double,double>& a,const pair<double,double>& b,const pair<double,double>& c)
{
return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
bool comp(const pair<double,double>& a,const pair<double,double>& b)
{
return cross_prod(v[1],a,b)<0;
}
int main()
{
f>>n;
pos=1;
for(i=1;i<=n;i++)
{
f>>a>>b;
v[i]=mp(a,b);
if(v[i]<v[pos])pos=i;
}
swap(v[pos],v[1]);
sort(v+2,v+n+1,comp);
s[1]=v[1];
s[2]=v[2];
head=2;
for(i=3;i<=n;i++)
{
while(head>=2&&cross_prod(s[head-1],s[head],v[i])>0)head--;
s[++head]=v[i];
}
g<<head<<'\n';
g<<fixed<<setprecision(9);
for(i=head;i;i--)
g<<s[i].x<<" "<<s[i].y<<'\n';
f.close();
g.close();
return 0;
}