Pagini recente » Cod sursa (job #534221) | Cod sursa (job #2547432) | Cod sursa (job #447312) | Cod sursa (job #818937) | Cod sursa (job #3226684)
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
using namespace std;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
int n,s[120005],k,pmin;
pair<double,double>v[120005];
double det(double x1,double y1,double x2,double y2,double x3,double y3)
{
return (x2-x1)*(y3-y1)-(y2-y1)*(x3-x1);
}
int cmp(pair<double,double>a,pair<double,double>b)
{
return det(v[1].first,v[1].second,a.first,a.second,b.first,b.second)<0;
}
int main()
{
cin>>n;
pmin=0;
v[0].first=1e9+2;
v[0].second=1e9+2;
for(int i=1; i<=n; i++)
{
cin>>v[i].first>>v[i].second;
if(v[i].first<v[pmin].first)
pmin=i;
else if(v[i].first==v[pmin].first&&v[i].second<v[pmin].second)
pmin=i;
}
swap(v[1],v[pmin]);
sort(v+2,v+n+1,cmp);
s[1]=1;
s[2]=2;
k=2;
for(int i=3;i<=n;i++)
{
while(k>2&&det(v[s[k-1]].first,v[s[k-1]].second,v[s[k]].first,v[s[k]].second,v[i].first,v[i].second)>0)
k--;
s[++k]=i;
}
cout<<k<<'\n';
for(int i=k;i>=1;i--)
cout<<fixed<<setprecision(6)<<v[s[i]].first<<" "<<v[s[i]].second<<'\n';
return 0;
}