Pagini recente » Cod sursa (job #2034551) | Cod sursa (job #1608039) | Cod sursa (job #1698760) | Cod sursa (job #2493003) | Cod sursa (job #2953532)
#include <stdio.h>
#include <algorithm>
struct Point {
double x, y;
};
#define MAXN 120'000
#define INF 1'000'000'001
Point points[MAXN];
Point origin;
Point st[MAXN];
int st_size;
bool cmp_angle(const Point& a, const Point& b) {
if(a.x == origin.x && a.y == origin.y) // tinem originea prima in vector
return true;
return (a.y - origin.y) * (b.x - origin.x) < (b.y - origin.y) * (a.x - origin.x);
}
bool trig_ord(const Point& a, const Point& b, const Point& c) {
return (b.y - a.y) * (c.x - b.x) < (c.y - b.y) * (b.x - a.x);
}
int main() {
FILE *fin, *fout;
int n, i;
fin = fopen("infasuratoare.in", "r");
origin = {INF, INF};
fscanf(fin, "%d", &n);
for(i = 0; i < n; i++) {
fscanf(fin, "%lf%lf", &points[i].x, &points[i].y);
if(points[i].y < origin.y || (points[i].y == origin.y && points[i].x < origin.x))
origin = points[i];
}
fclose(fin);
std::sort(points, points + n, cmp_angle);
Point a, b, c;
st[st_size++] = {origin.x, origin.y};
st[st_size++] = {points[1].x, points[1].y};
for(i = 2; i < n; i++) {
c = {points[i].x, points[i].y};
a = {st[st_size - 2].x, st[st_size - 2].y};
b = {st[st_size - 1].x, st[st_size - 1].y};
while(!trig_ord(a, b, c)) {
st_size--;
a = {st[st_size - 2].x, st[st_size - 2].y};
b = {st[st_size - 1].x, st[st_size - 1].y};
}
st[st_size++] = {c.x, c.y};
}
fout = fopen("infasuratoare.out", "w");
fprintf(fout, "%d\n", st_size);
for(i = 0; i < st_size; i++)
fprintf(fout, "%lf %lf\n", st[i].x, st[i].y);
fclose(fout);
return 0;
}