Pagini recente » Cod sursa (job #397728) | Cod sursa (job #1492849) | Cod sursa (job #1384005) | Cod sursa (job #2073616) | Cod sursa (job #3144769)
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
pair <double,double> v[120001];
int st[120001],afis[120001];
double triunghi(int p1,int p2,int p3)
{
return (v[p1].first-v[p2].first)*(v[p1].second-v[p3].second)-(v[p1].second-v[p2].second)*(v[p1].first-v[p3].first);
}
int main()
{
int n,i,cnt=0,vf=0;
in>>n;
for(i=1;i<=n;i++)
in>>v[i].first>>v[i].second;
sort(v+1,v+n+1);
vf=0;
st[++vf]=1;
st[++vf]=2;
for(i=3;i<=n;i++)
{
while(vf>1&&triunghi(st[vf-1],st[vf],i)<-1e-12)
vf--;
st[++vf]=i;
}
cnt=vf;
for(i=1;i<=vf;i++)
afis[i]=st[i];
vf=0;
st[++vf]=n;
st[++vf]=n-1;
for(i=n-2;i>=1;i--)
{
while(vf>1&&triunghi(st[vf-1],st[vf],i)<-1e-12)
vf--;
st[++vf]=i;
}
for(i=2;i<=vf-1;i++)
afis[++cnt]=st[i];
out<<cnt<<'\n';
out<<setprecision(6)<<fixed;
for(i=1;i<=cnt;i++)
out<<v[afis[i]].first<<" "<<v[afis[i]].second<<'\n';
return 0;
}