Cod sursa(job #3165429)

Utilizator adimiclaus15Miclaus Adrian Stefan adimiclaus15 Data 6 noiembrie 2023 10:37:17
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.54 kb
#include<fstream>
#include<vector>
#include<algorithm>
#include<iomanip>
using namespace std;

double xmin = 1000000000.0, ymin;

ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");

struct Point {
	double x, y;
};
vector<Point> vp;

double getDelta(Point p1,Point p2,Point p3) {
	vector<vector<double>> mat =
	{
		{p1.x,p1.y,1},
		{p2.x,p2.y,1},
		{p3.x,p3.y,1},
		{p1.x,p1.y,1},
		{p2.x,p2.y,1},
	};
	return mat[0][0] * mat[1][1] * mat[2][2] + mat[1][0] * mat[2][1] * mat[3][2] + mat[2][0] * mat[3][1] * mat[4][2] -
		(mat[0][2] * mat[1][1] * mat[2][0] + mat[1][2] * mat[2][1] * mat[3][0] + mat[2][2] * mat[3][1] * mat[4][0]);
}

vector<Point> v1;

int main() {

	int i, j, n;
	double x, y, nr;

	cin >> n;

	for (i = 0; i < n; i++) {
		cin >> x >> y;
		if (xmin > x) {
			xmin = x;
			ymin = y;
		}
		vp.push_back({ x,y });
	}

	for (i = 0; i < n; i++) {
		if (vp[i].x == xmin && vp[i].y == ymin) {
			vp.erase(vp.begin() + i);
			n--;
		}
	}

	sort(vp.begin(), vp.end(), [](Point& p1, Point& p2) {
		return (getDelta({ xmin,ymin }, p1,p2) > 0);
	});

	v1.push_back({ xmin,ymin });
	v1.push_back({ vp[0].x,vp[0].y});

	for (i = 1; i < n; i++) {
		Point p2 = *v1.rbegin();
		Point p1 = *(v1.rbegin()+1);
		while (vl.size() >= 2 && getDelta(*(v1.rbegin() + 1), *v1.rbegin(), vp[i]) < 0) {
			v1.pop_back();
		}
		v1.push_back(vp[i]);
	}

	cout << v1.size() << "\n";

	cout << fixed <<setprecision(12);

	for (auto p : v1) {
		cout << p.x << " " << p.y << "\n";
	}

	return 0;
}