Cod sursa(job #2636748)

Utilizator irimia_alexIrimia Alex irimia_alex Data 19 iulie 2020 16:15:41
Problema Infasuratoare convexa Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.75 kb
#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

FILE* fin, * fout;

struct point {
	double x, y;
};

vector<point> v;
vector<int> poly;

double cross_product(point origin, point a, point b) {
	double x1 = origin.x - a.x;
	double x2 = origin.x - b.x;
	double y1 = origin.y - a.y;
	double y2 = origin.y - b.y;

	return (y2 * x1 - y1 * x2);
}

int side(point origin, point end, point p) {
	double prod = cross_product(origin, end, p);
	if (prod > 0) return 1;
	if (prod < 0) return -1;
	return 0;
}

double dist(point a, point b) {
	double x = a.x - b.x, y = a.y - b.y;
	x *= x;
	y *= y;
	return x + y;
}

int find_left_most() {
	int i = 0;
	for(int j=1;j<v.size();++j)
		if(v[j].x<v[i].x || (v[j].x==v[i].x && v[j].y<v[i].y))
			i=j;
	return i;
}

void convex_hull() {
	int start = find_left_most();
	poly.push_back(start);
	bool done = false;
	int current = start, next = (start + 1) % v.size();
	while (!done) {
		for (int i = 0;i < v.size();++i) {
			if (i == current || i == next) continue;
			int s = side(v[current], v[next], v[i]);
			if (s > 0)
				next = i;
			else if (s == 0) {
				if (dist(v[current], v[i]) > dist(v[current], v[next]))
					next = i;
			}
		}
		if (next == poly[0])
			done = true;
		else {
			poly.push_back(next);
			current = next;
			next = 0;
		}
	}

	fprintf(fout,"%i\n", poly.size());
	reverse(poly.begin() + 1, poly.end());
	for(int i:poly)
		fprintf(fout,"%lf %lf\n",v[i].x,v[i].y);
}

int main() {
	fin = fopen("infasuratoare.in", "r");
	fout = fopen("infasuratoare.out", "w");

	int n;
	fscanf(fin, "%i", &n);
	while (n--) {
		double x, y;
		fscanf(fin, "%lf %lf", &x, &y);
		v.push_back({ x,y });
	}

	convex_hull();

	return 0;
}