Pagini recente » Cod sursa (job #2024328) | Cod sursa (job #2628828) | Cod sursa (job #2072683) | Cod sursa (job #667508) | Cod sursa (job #3241949)
#include <bits/stdc++.h>
using namespace std;
const int MAX = 2 * 1e5;
struct point{
double x, y;
}A[MAX + 3];
int N;
vector<int>s;
vector<int>s1;
bool v[MAX + 3];
double F(point O, point A, point B) {
return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x);
}
set<int>s3;
bool cmp(point a, point b) {
if(a.x < b.x) return true;
if(a.x == b.x) return a.y < b.y;
}
int main() {
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
cin >> N;
for(int i = 1; i <= N; i++) {
cin >> A[i].x >> A[i].y;
}
sort(A + 1, A + N + 1, cmp);
s.push_back(2);
s.push_back(1);
for(int i = 1; i <= N; i++) {
while(s.size() >= 2 && F(A[s[s.size() - 2]], A[s[s.size() - 1]], A[i]) < 0) {
s.pop_back();
}
s.push_back(i);
}
for(auto i : s) {
s3.insert(i);
}
for(int i = N; i >= 1; i--) {
while(s1.size() >= 2 && F(A[s1[s1.size() - 2]], A[s1[s1.size() - 1]], A[i]) < 0) {
s1.pop_back();
}
s1.push_back(i);
}
for(auto i : s1) {
s3.insert(i);
}
cout << setprecision(8);
cout << s3.size() << '\n';
for(auto i : s3) {
cout << A[i].x << ' ' << A[i].y << '\n';
}
}