Pagini recente » Cod sursa (job #1322593) | Cod sursa (job #1256640) | Cod sursa (job #1320585) | Cod sursa (job #1251848) | Cod sursa (job #3358750)
#include <bits/stdc++.h>
using namespace std;
struct pct
{
long double x,y;
};
bool cmp(pct a,pct b)
{
if(a.x!=b.x) return a.x<b.x;
return a.y<b.y;
}
pct p[120001];
vector<pct> h;
long double sens(pct a,pct b,pct c)
{
return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
#define cin fin
#define cout fout
int n;
int main()
{
cin>>n;
for(int i=0;i<n;i++)
cin>>p[i].x>>p[i].y;
sort(p,p+n,cmp);
for(int i=0;i<n;i++)
{
while(h.size()>=2 && sens(h[h.size()-2],h[h.size()-1],p[i])<=0)
h.pop_back();
h.push_back(p[i]);
}
int k=h.size();
for(int i=n-2;i>=0;i--)
{
while(h.size()>k && sens(h[h.size()-2],h[h.size()-1],p[i])<=0)
h.pop_back();
h.push_back(p[i]);
}
h.pop_back();
cout<<h.size()<<'\n';
cout<<fixed<<setprecision(6);
for(int i=0;i<h.size();i++)
cout<<h[i].x<<' '<<h[i].y<<'\n';
return 0;
}