Pagini recente » Cod sursa (job #1311114) | Cod sursa (job #904070) | Cod sursa (job #986829) | Cod sursa (job #2069016) | Cod sursa (job #2875394)
#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>> Hull;
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;
}
void 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++;
for(int j = 0;j < pre.size(); ++j)
cout << pre[j].first << ' ' << pre[j].second << '\n';
cout << '\n';
}
for(int i = 0;i < pre.size(); ++i) Hull.add(pre[i]);
}
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());
Solve();
reverse(v.begin(),v.end());
Hull.pop_back();
Solve();
Hull.pop_back();
cout << Hull.size() << '\n';
for(int i = 0;i < Hull.size(); ++i, cout << Hull[i-1].first << ' ' << Hull[i-1].second << '\n');
}