Pagini recente » Cod sursa (job #199473) | Cod sursa (job #2677674) | Cod sursa (job #928108) | Cod sursa (job #2648523) | Cod sursa (job #1906865)
#include <bits/stdc++.h>
#define point pair < double, double >
#define x first
#define y second
using namespace std;
const int nmax = 12e4 + 10;
int n;
int last, v[nmax];
point p[nmax];
void input() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i)
scanf("%lf %lf", &p[i].x, &p[i].y);
}
double det(point a, point b, point c) {
return a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y);
}
bool sgn(int a, int b, int c) {
return det(p[a], p[b], p[c]) < 0.0;
}
void run_convexHull() {
sort(p + 1, p + n + 1);
v[++last] = 1;
for (int i = 2; i <= n; ++i) {
while (last > 1 && sgn(v[last-1], v[last], i))
last--;
v[++last] = i;
}
for (int i = n - 1; i; --i) {
while (last > 1 && sgn(v[last-1], v[last], i))
last--;
v[++last] = i;
}
last--;
}
void output() {
printf("%d\n", last);
for (int i = 1; i <= last; ++i)
printf("%.10f %.10f\n", p[v[i]].x, p[v[i]].y);
}
int main() {
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
input();
run_convexHull();
output();
return 0;
}