Cod sursa(job #2636765)

Utilizator irimia_alexIrimia Alex irimia_alex Data 19 iulie 2020 18:49:34
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.66 kb
#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

FILE* fin, * fout;

struct point {
	double x, y;
};

vector<point> v;
vector<point> 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;
}

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

void swap(point& a, point& b) {
	point aux = a;
	a = b;
	b = aux;
}

void convex_hull() {
	int start = find_bottom_most();
	swap(v[0], v[start]);
	auto cmp = [p = v[0]](point& a, point& b){return side(p, a, b) == 1;};
	sort(v.begin() + 1, v.end(), cmp);
	poly.push_back(v[0]);
	poly.push_back(v[1]);
	poly.push_back(v[2]);
	point x = v[1], y = v[2];
	for (int i = 3;i < v.size();++i) {
		while (side(x, y, v[i]) == -1) {
			poly.pop_back();
			x = poly[poly.size() - 2];
			y = poly[poly.size() - 1];
		}
		poly.push_back(v[i]);
		x = poly[poly.size() - 2];
		y = poly[poly.size() - 1];
	}
	fprintf(fout, "%i\n", poly.size());
	for (point p : poly)
		fprintf(fout, "%lf %lf\n", p.x, p.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;
}