Pagini recente » Cod sursa (job #1267764) | Cod sursa (job #665540) | Solutii preONI 2007, Runda 1 | Cod sursa (job #1578844) | Cod sursa (job #1815418)
#include <cstdio>
#include <algorithm>
#include <vector>
#define point pair < double, double >
#define x first
#define y second
using namespace std;
const int nmax = 1e5 + 10;
int n;
point a[nmax];
vector < int > v;
void input() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i)
scanf("%lf %lf", &a[i].x, &a[i].y);
}
int determinant(point a, point b, point c) {
return (a.x * b.y + b.x * c.y + c.x * a.y - b.y * c.x - a.y * b.x - a.x * c.y < 0);
}
int det(int idx1, int idx2, int idx3) {
return determinant(a[idx1], a[idx2], a[idx3]);
}
void run_convexHull() {
sort(a + 1, a + n + 1);
v.push_back(1);
for (int i = 2; i <= n; ++i) {
while ((int)v.size() > 1 && det(v[(int)v.size()-2],v.back(), i))
v.pop_back();
v.push_back(i);
}
for (int i = n - 1; i ; --i) {
while ((int)v.size() > 1 && det(v[(int)v.size()-2],v.back(), i))
v.pop_back();
v.push_back(i);
}
v.pop_back();
}
void output() {
printf("%d\n", (int)v.size());
for (auto &it : v)
printf("%.12f %.12f\n", a[it].x, a[it].y);
}
int main() {
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
input();
run_convexHull();
output();
return 0;
}