Pagini recente » Cod sursa (job #3358681) | Borderou de evaluare (job #1322619) | Cod sursa (job #3357104) | Cod sursa (job #3358160) | Cod sursa (job #3358861)
#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 f("infasuratoare.in");
ofstream g("infasuratoare.out");
#define cin f
#define cout g
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;
}