Cod sursa(job #3165434)

Utilizator Luca07Nicolae Luca Luca07 Data 6 noiembrie 2023 10:47:37
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.62 kb
#include<fstream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<stack>
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]);
}

stack<Point> st;


bool check(Point p3) {
	Point p2 = st.top();
	st.pop();
	Point p1 = st.top();
	st.push(p2);
	return (getDelta(p1, p2, p3) < 0);
}

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--;
			break;
		}
	}

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

	st.push({ xmin,ymin });
	st.push({ vp[0].x,vp[0].y });

	for (i = 1; i < n; i++) {
		while (st.size() >= 2 &&check( vp[i])) {
			st.pop();
		}
		st.push(vp[i]);
	}

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

	cout << fixed << setprecision(12);

	while (!st.empty()) {
		cout << st.top().x << " " << st.top().y << "\n";
		st.pop();
	}

	return 0;
}