Pagini recente » Cod sursa (job #798001) | Cod sursa (job #2177614) | Cod sursa (job #2367734) | Cod sursa (job #729943) | Cod sursa (job #1731851)
#include <bits/stdc++.h>
using namespace std;
typedef long double ld;
#define all(x) x.begin(),x.end()
#define halt(...) {fo << (__VA_ARGS__) << '\n';exit(0);}
#define db(n) cerr << #n << " = " << n << '\n'
struct p
{
ld x,y;
};
ld ddd(p x, p y, p z)
{
return x.x*y.y+y.x*z.y+z.x*x.y-x.y*y.x-y.y*z.x-z.y*x.x;
}
int n;
vector<p> v;
int main()
{
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
ios_base::sync_with_stdio(0); cin.tie(0);
cin>>n;
v.resize(n);
for (int i=0; i<n; i++)
cin>>v[i].x>>v[i].y;
sort( all(v), [](p x, p y){ if (x.x!=y.x) return x.x<y.x; return x.y<y.y;});
sort( v.begin()+1, v.end(), [=](p x, p y){ return ddd(v[0],x,y)>0;});
int m = 1;
vector<p> h = {v[0],v[0]};
for (int i=1; i<n; i++)
{
while (i<n && ddd(h[m-1],h[m],v[i])<0)
if (m>1) h.pop_back(),m--;
else i++;
if (i<n) h.push_back(v[i]),m++;
}
h.erase(h.begin());
cout<<h.size()<<'\n';
cout<<fixed<<setprecision(9);
for (auto i:h)
cout<<i.x<<' '<<i.y<<'\n';
return 0;
}