Pagini recente » Cod sursa (job #1958790) | Cod sursa (job #1789254) | Cod sursa (job #40512) | Cod sursa (job #99695) | Cod sursa (job #2011905)
#include <cstdio>
#include <algorithm>
#include <stack>
using namespace std;
const int nmax = 120000;
struct Point {
double x, y;
bool operator< (Point other) const {
if(x != other.x) {
return y < other.y;
}
return x < other.x;
}
} v[1 + nmax];
int st[1 + nmax];
double det3(Point a, Point b, Point c) {
double adun, scad;
adun = a.x * b.y + a.y * c.x + b.x * c.y;
scad = a.x * c.y + a.y * b.x + b.y * c.x;
return (adun - scad);
}
bool cmp(Point a, Point b) {
return (det3(v[1], a, b) > 0);
}
int main() {
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
int n;
scanf("%d", &n);
for(int i = 1; i <= n; ++ i) {
scanf("%lf%lf", &v[i].x, &v[i].y);
if(i > 1 && v[i] < v[1]) {
swap(v[1], v[i]);
}
}
sort(v + 2, v + n + 1, cmp);
int nsol = 2, j = 3;
st[1] = 1, st[2] = 2;
while(j <= n) {
if(det3(v[st[nsol - 1]], v[st[nsol]], v[j]) > 0) {
st[++ nsol] = j ++;
} else {
-- nsol;
}
}
printf("%d\n", nsol);
for(int i = 1; i <= nsol; ++ i) {
printf("%.6lf %.6lf\n", v[st[i]].x, v[st[i]].y);
}
return 0;
}