Pagini recente » Cod sursa (job #2374724) | Cod sursa (job #1145373) | Cod sursa (job #2098682) | Cod sursa (job #2827812) | Cod sursa (job #2539751)
#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];
inline long double cross(pair<long double, long double> a, pair<long double, long double> b, pair<long double, long double> c){
return (b.first - a.first) * (c.second - a.second) - (b.second - a.second) * (c.first - a.first);
}
int main() {
ios_base::sync_with_stdio(0);
cin>>n;
for(int x = 0; x<n; x++)
cin>>points[x].first>>points[x].second;
int tmp = 0;
for(int x = 1;x<n;x++){
if(points[tmp] > points[x])
tmp = x;
}
swap(points[0], points[tmp]);
{
auto first = points[0];
sort(points + 1, points + n, [first](pair<long double, long double> a, pair<long double, long double> b) {
return cross(first, a, b) < 0;
});
}
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) && (cross(hull[hull.size() - 2], hull.back(), points[x]) > 0)){
hull.pop_back();
}
hull.push_back(points[x]);
}
cout<<setprecision(20)<<hull.size()<<'\n';
for(auto p = hull.rbegin();p!=hull.rend();p++)
cout<<p->first<<' '<<p->second<<'\n';
return 0;
}