Pagini recente » Cod sursa (job #1309620) | Cod sursa (job #2294870) | Cod sursa (job #2952542) | Cod sursa (job #1544677) | Cod sursa (job #2155496)
#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];
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) {
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;
point min = point(INT_MAX, INT_MAX);
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) {
min = p[i];
} else if (p[i].y == min.y && p[i].x < min.x) {
min = p[i];
}
}
fclose(f);
//fprintf(stderr, "%lf %lf\n", min.x, min.y);
for (i = 1; i <= N; i++) {
p[i].x -= min.x;
p[i].y -= min.y;
p[i].ang = get(p[i]);
//fprintf(stderr, "%d %d %f\n", p[i].x, p[i].y, p[i].ang);
}
sort(p + 1, p + N + 1, cmp);
/*
for (i = 1; i <= N; i++) {
fprintf(stderr, "%lf %lf -> %lf\n", p[i].x, p[i].y, p[i].ang);
}
*/
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 + min.x, stack[i].y + min.y);
}
fclose(stdout);
return 0;
}