Cod sursa(job #2953532)

Utilizator mihaipriboimihailucapriboi mihaipriboi Data 11 decembrie 2022 17:08:28
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.57 kb
#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;
}