Pagini recente » Cod sursa (job #14307) | Cod sursa (job #659550) | Cod sursa (job #890317) | Cod sursa (job #1140218) | Cod sursa (job #1920210)
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
double Determinant(const pair<double, double>& a, const pair<double, double>& b, const pair<double, double>& c) {
return (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y);
}
int main() {
#ifdef INFOARENA
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
#endif
cin.tie(0);
ios_base::sync_with_stdio(false);
cout.precision(12);
cout.setf(ios::fixed, ios::floatfield);
int n;
cin >> n;
vector<pair<double, double>> Points(n);
for(auto &point : Points)
cin >> point.x >> point.y;
sort(begin(Points), end(Points));
vector<int> LowerStk;
for(int i = 0; i < (int)Points.size(); ++i) {
int m = (int)LowerStk.size();
while(m > 1 && Determinant(Points[LowerStk[m - 2]], Points[LowerStk[m - 1]], Points[i]) > 1e-12) {
LowerStk.pop_back();
m--;
}
LowerStk.push_back(i);
}
vector<int> UpperStk;
for(int i = (int)Points.size() - 1; i >= 0; --i) {
int m = (int)UpperStk.size();
while(m > 1 && Determinant(Points[UpperStk[m - 2]], Points[UpperStk[m - 1]], Points[i]) < 1e-12) {
UpperStk.pop_back();
m--;
}
UpperStk.push_back(i);
}
LowerStk.pop_back();
UpperStk.pop_back();
cout << LowerStk.size() + UpperStk.size() << '\n';
for(const int &a : LowerStk)
cout << Points[a].x << ' ' << Points[a].y << '\n';
for(const int& a : UpperStk)
cout << Points[a].x << ' ' << Points[a].y << '\n';
}