Pagini recente » Cod sursa (job #1119297) | Cod sursa (job #435589) | Cod sursa (job #1159104) | Cod sursa (job #2534362) | Cod sursa (job #1398110)
#include <iostream>
#include <cstdio>
#include <vector>
#include <tuple>
#include <algorithm>
using namespace std;
typedef tuple<double,double> point;
bool ccw(point a, point b, point c)
{
return (get<0>(b)-get<0>(a))*(get<1>(c)-get<1>(b))
> (get<1>(b)-get<1>(a))*(get<0>(c)-get<0>(b));
}
vector<int> getcvh(const vector<point>& pts)
{
int n = pts.size();
vector<int> cvh(n);
int cnt = 0;
for (int i = 0; i < n; i++) {
while (cnt >= 2 && !ccw(pts[cvh[cnt-2]], pts[cvh[cnt-1]], pts[i])) {
cnt--;
}
cvh[cnt++] = i;
}
int lcnt = cnt-1;
for (int i = n-1; i >= 0; i--) {
while (cnt >= lcnt+2 && !ccw(pts[cvh[cnt-2]], pts[cvh[cnt-1]], pts[i])) {
cnt--;
}
cvh[cnt++] = i;
}
cnt--;
cvh.resize(cnt);
return cvh;
}
int main()
{
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
cin.sync_with_stdio(false);
int n;
cin >> n;
vector<point> pts(n);
for (int i = 0; i < n; i++) {
cin >> get<0>(pts[i]) >> get<1>(pts[i]);
}
sort(pts.begin(), pts.end());
auto cvh = getcvh(pts);
printf("%d\n", cvh.size());
for (int i: cvh) {
printf("%.6f %.6f\n", get<0>(pts[i]), get<1>(pts[i]));
}
}