Cod sursa(job #2924443)

Utilizator lolismekAlex Jerpelea lolismek Data 2 octombrie 2022 18:02:39
Problema Gradina Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.32 kb
// TODO: debug lol
#include <iostream>
#include <fstream>
#include <cmath>
#include <vector>
#include <algorithm>

#define double long double
#define int long long

using namespace std;

ifstream fin("gradina.in");
ofstream fout("gradina.out");

namespace Geometry{
	struct Point{
		double x, y;
	};

	double dist(Point p1, Point p2){
		double dx = p1.x - p2.x, dy = p1.y - p2.y;
		return sqrt(dx * dx + dy * dy);
	}

	double area(Point p1, Point p2, Point p3){
		return p1.x * (p2.y - p3.y) + p2.x * (p3.y - p1.y) + p3.x * (p1.y - p2.y);
	}

	double polygonArea(vector <Point> v){
		double A = 0;
		int n = (int)v.size();
		for(int i = 0; i < n; i++)
			A += area(v[i], v[(i + 1) % n], {0, 0});
		return A / 2;
	}

	bool cmp(Point a, Point b){
		if(a.x == b.x)
			return a.y < b.y;
		return a.x < b.x;
	}

	vector <Point> convexHull(vector <Point> v){
		int n = (int)v.size();
		sort(v.begin(), v.end(), cmp);

		vector <Point> up, down;
		up.push_back(v[1]);
		down.push_back(v[1]);

		for(int i = 1; i < n; i++){
			while((int)up.size() > 1 && area(up[(int)up.size() - 2], up[(int)up.size() - 1], v[i]) <= 0)
				up.pop_back();
			up.push_back(v[i]);
			while((int)down.size() > 1 && area(down[(int)down.size() - 2], down[(int)down.size() - 1], v[i]) >= 0)
				down.pop_back();
			down.push_back(v[i]);
		}

		vector <Point> CH = up;
		for(int i = (int)down.size() - 2; i >= 1; i--)
			CH.push_back(down[i]);

		reverse(CH.begin(), CH.end());

		return CH;
	}		
}

string Min(string a, string b){
	for(int i = 0; i < min((int)a.size(), (int)b.size()); i++)
		if(a[i] < b[i])
			return a;
		else if(b[i] < a[i])
			return b;

	if((int)a.size() < (int)b.size())
		return a;
	return b;
}

vector <Geometry::Point> v;

signed main(){

	int n;
	fin >> n;

	for(int i = 1; i <= n; i++){
		Geometry::Point point;
		fin >> point.x >> point.y;
		v.push_back(point);
	}

	// sort(v.begin(), v.end(), Geometry::cmp);

	double ans = 1e18;
	string sAns = "";

	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= n; j++)
			if(i != j){
				vector <Geometry::Point> down, up;
				down.push_back(v[i]);
				down.push_back(v[j]);

				string config1(n + 1, 0), config2(n + 1, 0);
				config1[i] = 'I', config1[j] = 'I';
				config2[i] = 'V', config2[j] = 'V';

				for(int k = 1; k <= n; k++)
					if(k != i && k != j){
						if(Geometry::area(v[i], v[j], v[k]) <= 0)
							down.push_back(v[k]),
							config1[k] = 'I', config2[k] = 'V';
						else
							up.push_back(v[k]),
							config1[k] = 'V', config2[k] = 'I';
					}

				if((int)down.size() > 1 && (int)up.size() > 1){
					vector <Geometry::Point> poli1 = Geometry::convexHull(down),
											 poli2 = Geometry::convexHull(up);


					for(auto p : down)
						cout << p.x << ' ' << p.y << endl;

					double area1 = Geometry::polygonArea(poli1), 
						   area2 = Geometry::polygonArea(poli2);

					double diff = abs(area1 - area2);

					if(diff < ans){
						ans = diff;
						sAns = Min(config1, config2);
					}else if(diff == ans)
						sAns = Min(sAns, Min(config1, config2));
				}
			}
		
	fout << ans << '\n';
	
	return 0;
}

/*
	Eram odata in Padurea Baneasa si am gasit scrijelit pe un copac astfel: 
				" - Oricare doua poligoane convexe in plan pot fi separate de o dreapta... "
*/