Pagini recente » Cod sursa (job #701908) | Cod sursa (job #2374392) | Cod sursa (job #2875408)
#include <bits/stdc++.h>
#define FILES freopen("infasuratoare.in","r",stdin);\
freopen("infasuratoare.out","w",stdout);
#define add emplace_back
#define mp make_pair
#define fastio ios_base::sync_with_stdio(NULL),cin.tie(NULL),cout.tie(NULL);
using namespace std;
vector<pair<double,double>> v;
vector<pair<double,double>> Uh,Dh;
int n;
double a,b;
double cp(pair<double,double>a,pair<double,double> b,pair<double,double>c)
{
a.first -= c.first, b.first -= c.first;
a.second -= c.second, b.second -= c.second;
return a.first * b.second - a.second * b.first;
}
vector<pair<double,double>> Solve()
{
vector<pair<double,double>> pre;
int sz = 0;
for(int i = 0;i < v.size(); ++i)
{
if(pre.size() < 2)
{
sz++;
pre.add(v[i]);
continue;
}
while(pre.size() >= 2 && cp(pre[sz-1],v[i],pre[sz-2]) > 0.0)
sz--,pre.pop_back();
pre.add(v[i]);
sz++;
}
return pre;
}
bool cmp(pair<double,double> a,pair<double,double> b)
{
return cp(a,b,{0.0,0.0}) >= 0;
}
int main()
{
fastio
FILES
cin >> n;
for(int i = 1;i <= n; ++i, cin >> a >> b, v.add(mp(a,b)));
sort(v.begin(),v.end());
Uh = Solve();
reverse(v.begin(),v.end());
Dh = Solve();
reverse(Uh.begin(),Uh.end());
reverse(Dh.begin(),Dh.end());
Uh.pop_back();
Dh.pop_back();
cout << Uh.size()+Dh.size() << '\n';
for(int i = 0;i < Dh.size(); ++i, cout << setprecision(12) << fixed << Dh[i-1].first << ' ' << Dh[i-1].second << '\n');
for(int i = 0;i < Uh.size(); ++i, cout << setprecision(12) << fixed << Uh[i-1].first << ' ' << Uh[i-1].second << '\n');
}