Pagini recente » Clasament concurs | Borderou de evaluare (job #2904503) | Borderou de evaluare (job #2247706) | Borderou de evaluare (job #2247705) | Cod sursa (job #323194)
Cod sursa(job #323194)
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
#define maxN 120100
#define EPS 1e-12
#define oo 15e8
typedef struct point point;
typedef struct line line;
int N;
struct point {
double x, y;
} P[maxN], PI;
struct line {
point a, b;
};
bool cmp_points (point a, point b) {
return (double)(a.x - PI.x) * (b.y - PI.y) > (double)(b.x - PI.x) * (a.y - PI.y);
}
double same (line l, point p1, point p2) {
int dx1, dx2, dy1, dy2, dx, dy;
dx = l.b.x - l.a.x; dy = l.b.y - l.a.y;
dx1 = p1.x - l.a.x; dy1 = p1.y - l.a.y;
dx2 = p2.x - l.b.x; dy2 = p2.y - l.b.y;
return (dx * dy1 - dy * dx1) * (dx * dy2 - dy * dx2);
}
void convex_hull () {
int M = 2, i;
line l;
for (i = 4; i <= N + 1; ++ i) {
M += 2;
do {
M --;
l.a = P[M];
l.b = P[M - 1];
} while (same (l, P[1], P[i]) < 0);
swap (P[M + 1], P[i]);
}
printf("%d\n", M);
for (i = 1; i <= M; ++ i)
printf("%.6lf %.6lf\n", P[i].x, P[i].y);
}
int main () {
int i, ind = 0;
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
scanf("%d", &N);
PI.x = oo; PI.y = oo;
for (i = 1; i <= N; ++ i) {
scanf("%lf%lf", &P[i].x, &P[i].y);
if (PI.y > P[i].y || (PI.y == P[i].y && PI.x > P[i].x)) { PI = P[i]; ind = i; };
}
swap (P[1], P[ind]);
sort (P + 2, P + N + 1, cmp_points);
P[N + 1] = P[1];
// for (i = 1; i <= N; ++ i)
// printf("%.2lf %.2lf\n", P[i].x, P[i].y);
convex_hull ();
}