Cod sursa(job #3226711)

Utilizator Luca07Nicolae Luca Luca07 Data 22 aprilie 2024 17:14:08
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.55 kb
#include<fstream>
#include<vector>
#include<algorithm>
#include<iomanip>
using namespace std;

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

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

Point origin = { INT32_MAX,INT32_MAX };


double compare(Point& p1, Point& p2) {
	return p1.x * p2.y - p1.y * p2.x;
}

bool isConvex(Point& p1, Point& p2, Point& p3) {
	Point p12 = { p2.x - p1.x,p2.y - p1.y };
	Point p23 = { p3.x - p2.x,p3.y - p2.y };
	return compare(p12, p23)>0;
}


int main() {

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

	cin >> n;
	for (i = 0; i < n; i++) {
		cin >> x >> y;
		if (origin.x > x||(origin.x == x&& origin.y > y)) {
			origin = { x,y };
		}
		points.push_back({ x,y });
	}

	sort(points.begin(), points.end(), [](Point& p1, Point& p2) {
		if (isConvex(origin, p1, p2)) {
			return true;
		}
		else if (isConvex(origin, p2, p1)) {
			return false;
		}
		return (abs(p1.x-origin.x)+ abs(p1.y - origin.y))< (abs(p2.x - origin.x) + abs(p2.y - origin.y));
	});

	vp.push_back(origin);
	vp.push_back(points[1]);
	i = 2;


	while (i < n) {
		double val = isConvex(vp[vp.size() - 2], vp[vp.size() - 1], points[i]);
		if (isConvex(vp[vp.size() - 2], vp[vp.size() - 1], points[i])) {
			vp.push_back(points[i]);
			i++;
		}
		else {
			vp.pop_back();
			if (vp.size() < 2) {
				vp.push_back(points[i]);
				i++;
			}
		}

	}

	cout << vp.size() << "\n";
	for (auto p : vp) {
		cout << fixed<<setprecision(12)<< p.x << " " << p.y<<"\n";
	}

	return 0;
}