Pagini recente » Profil alexandra_popoiu | Profil amarginean | Istoria paginii utilizator/dianapingu1 | Cod sursa (job #768043) | Cod sursa (job #1920171)
#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 a.x * b.y + b.x * c.y + c.x * a.y - c.x * b.y - a.x * c.y - b.x * 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(10);
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';
}