Pagini recente » Cod sursa (job #2173873) | Cod sursa (job #2059422) | Cod sursa (job #3281522) | Cod sursa (job #2519703) | Cod sursa (job #2174317)
#include <iostream>
#include <cstdio>
#include <algorithm>
#define NMAX 120005
using namespace std;
int N, st[NMAX], top;
bool viz[NMAX];
struct Point {
double x, y;
}a[NMAX];
bool cmp(Point A, Point B) {
if(A.y == B.y) {
return A.x < B.x;
}
return A.y < B.y;
}
void read() {
scanf("%d", &N);
for(int i = 1; i <= N; ++i) {
scanf("%lf %lf", &a[i].x, &a[i].y);
}
sort(a + 1, a + N + 1, cmp);
}
double det(int i, int j, int p) {
return a[p].x * (a[i].y - a[j].y) +
a[p].y * (a[j].x - a[i].x) +
a[i].x * a[j].y - a[j].x * a[i].y;
}
void insertInStack(int poz) {
while(top > 1 && det(st[top - 1], st[top], poz) < 0) {
viz[st[top]] = false;
top--;
}
viz[poz] = true;
st[++top] = poz;
}
void solve() {
st[1] = 1;
viz[2] = true;
st[2] = 2;
top = 2;
for(int i = 3; i <= N; ++i) {
insertInStack(i);
}
for(int i = N - 1; i >= 1; --i) {
if(!viz[i]) {
insertInStack(i);
}
}
}
void print() {
printf("%d\n", top - 1);
for(int i = 1; i < top; ++i) {
printf("%.13lf %.13lf\n", a[st[i]].x, a[st[i]].y);
}
}
int main()
{
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
read();
solve();
print();
return 0;
}