Pagini recente » Cod sursa (job #2883597) | Cod sursa (job #216013) | Cod sursa (job #2504374) | Cod sursa (job #65399) | Cod sursa (job #2539709)
#include <vector>
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
int n;
pair<long double, long double> points[120000];
int main() {
ios_base::sync_with_stdio(0);
cin>>n;
for(int x = 0; x<n; x++)
cin>>points[x].first>>points[x].second;
for(int x = 1; x<n; x++) {
if(points[x] < points[0])
swap(points[0], points[x]);
}
{
auto first = points[0];
sort(points + 1, points + n, [first](pair<long double, long double> a, pair<long double, long double> b) {
return (a.first - points[0].first)*(b.second - points[0].first) < (b.first - points[0].first)*(a.second - points[0].first);
});
}
vector<pair<long double, long double> > hull = {points[0], points[1]};
hull.reserve(n);
for(int x = 2;x<n;x++){
while((hull.size() > 2) && (0 < ((hull.back().first - hull[hull.size() - 2].first)*(points[x].second - hull[hull.size() - 2].second) - (hull.back().second - hull[hull.size() - 2].second)*(hull.back().first - hull[hull.size() - 2].first)))){
hull.pop_back();
}
hull.push_back(points[x]);
}
cout<<setprecision(20)<<hull.size()<<'\n';
for(auto p : hull)
cout<<p.first<<' '<<p.second<<'\n';
return 0;
}