Pagini recente » Cod sursa (job #1547337) | Cod sursa (job #1015680) | Cod sursa (job #421206) | Cod sursa (job #2770321) | Cod sursa (job #2921312)
#include <bits/stdc++.h>
using namespace std;
const int NMAX=120005;
pair<double,double> a[NMAX];
int n,i,j;
vector<int> hull;
int st[NMAX];
bool vis[NMAX];
const double EPS = 1e-12;
double det(pair<double,double> o, pair<double,double> a, pair<double,double> b)
{
return (a.first-o.first)*(b.second-o.second)-(a.second-o.second)*(b.first-o.first);
}
void solve()
{
cin>>n;
for(i=1;i<=n;i++)
cin>>a[i].first>>a[i].second;
sort(a+1,a+n+1);
st[1]=1;st[2]=st[0]=2;
vis[2]=1;
for(i=1;i<=n;i++)
{
if(vis[i])continue;
while(st[0]>=2&&det(a[st[st[0]-1]],a[st[st[0]]],a[i])<EPS)
vis[st[st[0]--]]=0;
st[++st[0]]=i;
vis[i]=1;
}
for(i=n-1;i>0;i--)
{
if(vis[i])continue;
while(st[0]>=2&&det(a[st[st[0]-1]],a[st[st[0]]],a[i])<EPS)
vis[st[st[0]--]]=0;
st[++st[0]]=i;
vis[i]=1;
}
cout<<--st[0]<<'\n';;
while(st[0]>0)
hull.push_back(st[st[0]--]);
reverse(hull.begin(),hull.end());
cout<<fixed<<setprecision(6);
hull.push_back(hull[0]);
for(i=1;i<hull.size();i++)
cout<<a[hull[i]].first<<' '<<a[hull[i]].second<<'\n';
}
signed main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
ios_base::sync_with_stdio(0);
cin.tie(0);
solve();
return 0;
}