Pagini recente » Cod sursa (job #143371) | Cod sursa (job #1785485) | Cod sursa (job #1539936) | Cod sursa (job #385974) | Cod sursa (job #1815546)
#include <cstdio>
#include <algorithm>
#include <vector>
#define point pair < double, double >
#define x first
#define y second
using namespace std;
const int nmax = 12e4 + 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);
}
bool determinant(point a, point b, point c) {
return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x) < 0;
}
bool 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;
}