Pagini recente » Cod sursa (job #138419) | Cod sursa (job #1658489) | Cod sursa (job #3175721) | Cod sursa (job #3282424) | Cod sursa (job #2558137)
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 120005;
const double eps = 1e-12;
int n;
pair<double,double> points[NMAX];
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int stac[NMAX];
int head = 0;
double crossProd(pair<double,double> a,pair<double,double>b,pair<double,double> o)
{
return (a.first-o.first)*(b.second-o.second)-
(b.first-o.first)*(a.second-o.second);
}
bool viz[NMAX];
void hull()
{
sort(points+1,points+n+1);
stac[1]=1;
stac[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 && crossProd(points[stac[head]],points[stac[head-1]],points[i])<=eps)
{
viz[stac[head--]]=false;
}
stac[++head]=i;
viz[i]=true;
}
}
int main()
{
fin>>n;
for(int i = 1;i<=n;i++) fin>>points[i].first>>points[i].second;
hull();
fout<<head-1<<'\n';
for(int i = head-1;i>=1;i--) fout<<fixed<<setprecision(6)<<points[stac[i]].first<<" "<<points[stac[i]].second<<'\n';
return 0;
}