Pagini recente » Cod sursa (job #3220340) | Cod sursa (job #1619049) | Cod sursa (job #2007544) | Cod sursa (job #1551325) | Cod sursa (job #2155503)
#include <stdio.h>
#include <climits>
#include <cmath>
#include <algorithm>
using std::sort;
struct point {
double x, y;
double ang;
point() {
this -> x = this -> y = 0;
this -> ang = 0;
}
point(float x, float y) {
this -> x = x;
this -> y = y;
}
};
#define MAX_N 120000
const double EPS = 1e-12;
const double pi = 3.141592654;
int N, ss;
point p[MAX_N + 1];
point stack[MAX_N + 1];
point min = point(INT_MAX, INT_MAX);
double MOD(double X) {
if (X > EPS) {
return X;
}
return -X;
}
double ccw(point p1, point p2, point p3) {
return (p2.x - p1.x) * (p3.y - p1.y) - (p3.x - p1.x) * (p2.y - p1.y);
}
double get(point curr) {
double ret = atan2(curr.y, curr.x);
if (curr.y >= -EPS) {
return ret;
}
return 2 * pi + ret;
}
bool cmp(point a, point b) {
if (ccw(min, a, b) > EPS) {
return 1;
} else if (MOD(ccw(min, a, b)) < EPS) {
return EPS < b.x - a.x;
}
//return (b.ang - a.ang > -EPS) || ((MOD(b.ang - a.ang) < EPS) && (-EPS < MOD(b.x) - MOD(a.x)));
}
int main(void) {
FILE *f = fopen("infasuratoare.in", "r");
int i, pos = 0;
fscanf(f, "%d", &N);
for (i = 1; i <= N; i++) {
fscanf(f, "%lf %lf", &p[i].x, &p[i].y);
if (p[i].y < min.y) {
pos = i;
min = p[i];
} else if (p[i].y == min.y && p[i].x < min.x) {
min = p[i];
pos = i;
}
}
fclose(f);
point tmp = p[1];
p[1] = min;
p[pos] = tmp;
sort(p + 2, p + N + 1, cmp);
for (i = 1; i <= N; i++) {
fprintf(stderr, "%lf %lf\n", p[i].x, p[i].y);
}
stack[ss++] = p[1];
stack[ss++] = p[2];
for (i = 3; i <= N; i++) {
while (ss > 2 && ccw(stack[ss - 2], stack[ss - 1], p[i]) < -EPS) {
ss--;
}
stack[ss++] = p[i];
}
freopen("infasuratoare.out", "w", stdout);
fprintf(stdout, "%d\n", ss);
for (i = 0; i < ss; i++) {
fprintf(stdout, "%lf %lf\n", stack[i].x, stack[i].y);
}
fclose(stdout);
return 0;
}