Pagini recente » Cod sursa (job #406701) | Cod sursa (job #2353466) | Cod sursa (job #579404) | Cod sursa (job #1399296) | Cod sursa (job #932576)
Cod sursa(job #932576)
#include <cstdio>
#include <algorithm>
#define MAX_N 120010
using namespace std;
struct punct {
double x, y;
} v[MAX_N];
int n, h, s[MAX_N];
int cmp (punct a, punct b) {
return (a.y - v[0].y) * (b.x - v[0].x) > (b.y - v[0].y) * (a.x - v[0].x);
}
int semn (int i, int j, int k) {
return (v[i].y - v[j].y) * v[k].x + (v[j].x - v[i].x) * v[k].y + v[i].x * v[j].y - v[j].x * v[i].y;
}
int main()
{
freopen ("infasuratoare.in","r",stdin);
freopen ("infasuratoare.out","w",stdout);
scanf ("%d", &n);
int i, p;
for (i = 0; i < n; i++) scanf ("%lf %lf", &v[i].x, &v[i].y);
p = 0;
for (i = 1; i < n; i++)
if (v[i].x < v[p].x || (v[i].x == v[p].x && v[i].y < v[p].y)) p = i;
swap (v[0], v[p]);
sort (v + 1, v + n, cmp);
for (i = 0; i < n; i++) {
while (h > 2 && semn (s[h-1], s[h], i) >= 0) h--;
s[++h] = i;
}
printf ("%d\n", h);
for (i = h; i > 0; i--) printf ("%lf %lf\n", v[s[i]].x, v[s[i]].y);
return 0;
}