Pagini recente » Cod sursa (job #2393612) | Cod sursa (job #233637) | Cod sursa (job #1393713) | Cod sursa (job #10545) | Cod sursa (job #2833446)
#include <bits/stdc++.h>
using namespace std;
struct Point {
double x, y;
};
bool cmp(Point a, Point b) {
if(a.x == b.x) return a.y < b.y;
return a.x < b.x;
}
double angle(Point a, Point b) {
return atan2(b.y - a.y, b.x - a.x);
}
int main() {
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
int n;
cin >> n;
vector<Point> v;
for(int i = 1; i <= n; i++) {
double x, y;
cin >> x >> y;
v.push_back({x,y});
}
sort(v.begin(),v.end(),cmp);
vector<Point> Upper;
vector<Point> Lower;
Upper.push_back(v[0]);
Lower.push_back(v[0]);
for(int i = 1; i < n; i++) {
// upper_bound
while(Upper.size() >= 2 && angle(Upper[Upper.size()-2],Upper[Upper.size()-1]) < angle(Upper[Upper.size()-1],v[i]) ) {
Upper.pop_back();
}
Upper.push_back(v[i]);
// lower_bound
while(Lower.size() >= 2 && angle(Lower[Lower.size()-2],Lower[Lower.size()-1]) > angle(Lower[Lower.size()-1],v[i]) ) {
Lower.pop_back();
}
Lower.push_back(v[i]);
}
cout << Lower.size() + Upper.size() - 2 << '\n';
cout << setprecision(12) << fixed;
for(auto &it : Lower)
cout << it.x << ' ' << it.y << '\n';
for(int i = Upper.size()-2; i >= 1; i--)
cout << Upper[i].x << ' ' << Upper[i].y << '\n';
return 0;
}