Pagini recente » Cod sursa (job #2658349) | Cod sursa (job #2643723) | Borderou de evaluare (job #804986) | Cod sursa (job #763610) | Cod sursa (job #1668723)
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <complex>
using namespace std;
typedef complex<double> Pnt;
typedef complex<double> Vec;
bool cmp(Pnt a, Pnt b) {
return real(a) < real(b)
|| real(a) == real(b) && imag(a) < imag(b);
}
double cross(Vec a, Vec b) {
return imag(conj(a)*b);
}
bool ccw(Pnt a, Pnt b, Pnt c) {
return cross(b-a, c-b) > 0;
}
vector<int> getcvh(const vector<Pnt>& pts) {
int n = pts.size();
if (pts.front() == pts.back()) return {0};
vector<int> cvh;
for (int i = 0; i < n; i++) {
while (cvh.size() >= 2
&& !ccw(pts[*(cvh.end()-2)], pts[*(cvh.end()-1)], pts[i]))
cvh.pop_back();
if (i != n-1) cvh.push_back(i);
}
// puts("b");
auto lcnt = cvh.size();
for (int i = n-1; i >= 0; i--) {
while (cvh.size() >= lcnt+2
&& !ccw(pts[*(cvh.end()-2)], pts[*(cvh.end()-1)], pts[i]))
cvh.pop_back();
if (i != 0) cvh.push_back(i);
}
// puts("c");
return cvh;
}
int main() {
#ifdef INFOARENA
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
#endif
ios::sync_with_stdio(false);
int n;
cin >> n;
vector<Pnt> pts(n);
for (int i = 0; i < n; i++) {
double x, y;
cin >> x >> y;
pts[i] = {x,y};
}
sort(pts.begin(), pts.end(), cmp);
auto cvh = getcvh(pts);
printf("%d\n", cvh.size());
for (int i: cvh) {
printf("%.6f %.6f\n", real(pts[i]), imag(pts[i]));
}
}