Cod sursa(job #1656582)

Utilizator iordache.bogdanIordache Ioan-Bogdan iordache.bogdan Data 19 martie 2016 16:07:10
Problema Gradina Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.49 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <cstring>

using namespace std;

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

const long long inf = 100000000000000000LL;

int n;

struct Point {
	int x, y, index;
	Point() {}
	Point(int x, int y) {
		this->x = x;
		this->y = y;
	}
	bool operator == (const Point a) const {
		return (x == a.x && y == a.y);
	}
	bool operator < (const Point a) const {
		return (y == a.y ? x < a.x : y < a.y);
	}
} points[300];

Point polygon1[300], polygon2[300];
int polygon1Count, polygon2Count;
int config[300], solConfig[300];

inline int det(const Point &a, const Point &b, const Point &c) {

	long long d = 1LL * (b.x - a.x)*(c.y - a.y) - 1LL * (b.y - a.y)*(c.x - a.x);

	if (d == 0)
		return 0;

	return (d < 0 ? -1 : 1);

}

inline long long realDet(const Point &a, const Point &b, const Point &c) {

	return 1LL * (b.x - a.x)*(c.y - a.y) - 1LL * (b.y - a.y)*(c.x - a.x);

}

int comp(int v[], int w[]) {

	for (int i = 1; i <= n; ++i)
		if (v[i] < w[i])
			return -1;
		else if (v[i] > w[i])
			return 1;

	return 0;

}

Point aux[300];
inline long long getArea(Point polygon[], int polygonCount) {

	if (polygonCount < 3)
		return inf;

	Point p1 = polygon[1];
	Point p2 = polygon[polygonCount];

	int left = 0, right = polygonCount + 1;

	for (int i = 1; i <= polygonCount; ++i) {

		if (i < polygonCount && polygon[i].y == polygon[i + 1].y && det(p1, p2, polygon[i])*det(p1, p2, polygon[i + 1]) == 1)
			return inf;

		if (det(p1, polygon[i], p2) >= 0)
			aux[++left] = polygon[i];
		else
			aux[--right] = polygon[i];

	}

	aux[polygonCount + 1] = aux[1]; aux[polygonCount + 2] = aux[2];

	for (int i = 1; i <= polygonCount; ++i)
		if (det(aux[i], aux[i + 1], aux[i + 2]) < 0)
			return inf;
	
	long long ret = 0;

	for (int i = 1; i <= polygonCount; ++i) {

		ret += realDet(Point(0, 0), aux[i], aux[i + 1]);

	}

	if (ret < 0)
		ret = -ret;

	return ret;

}

int main() {

	fin >> n;

	for (int i = 1; i <= n; ++i) {
		fin >> points[i].x >> points[i].y;
		points[i].index = i;
	}

	sort(points + 1, points + n + 1);

	long long minArea = inf;
	for (int i = 1; i <= n; ++i) {

		for (int j = i + 1; j <= n; ++j) {

			if (i == j)
				continue;

			Point p1 = points[i];
			Point p2 = points[j];

			polygon1Count = 0;
			polygon2Count = 0;

			for (int k = 1; k <= n; ++k) {

				if (points[k] == p1)
					polygon1[++polygon1Count] = points[k], config[points[k].index] = 1;
				else if (points[k] == p2)
					polygon2[++polygon2Count] = points[k], config[points[k].index] = 2;
				else if (det(points[k], p1, p2) == -1)
					polygon1[++polygon1Count] = points[k], config[points[k].index] = 1;
				else
					polygon2[++polygon2Count] = points[k], config[points[k].index] = 2;

			}

			long long area1 = getArea(polygon1, polygon1Count);
			long long area2 = getArea(polygon2, polygon2Count);

			if (area1 != inf && area2 != inf) {

				long long area = max(area1, area2) - min(area1, area2);
				
				if (area < minArea) {

					minArea = area;
					memcpy(solConfig, config, sizeof solConfig);

				}
				else if (area == minArea) {

					if (comp(config, solConfig) < 0)
						memcpy(solConfig, config, sizeof solConfig);

				}

			}

			polygon1Count = 0;
			polygon2Count = 0;

			for (int k = 1; k <= n; ++k) {

				if (points[k] == p2)
					polygon1[++polygon1Count] = points[k], config[points[k].index] = 1;
				else if (points[k] == p1)
					polygon2[++polygon2Count] = points[k], config[points[k].index] = 2;
				else if (det(points[k], p1, p2) == -1)
					polygon1[++polygon1Count] = points[k], config[points[k].index] = 1;
				else
					polygon2[++polygon2Count] = points[k], config[points[k].index] = 2;

			}

			area1 = getArea(polygon1, polygon1Count);
			area2 = getArea(polygon2, polygon2Count);

			if (area1 != inf && area2 != inf) {

				long long area = max(area1, area2) - min(area1, area2);

				if (area < minArea) {

					minArea = area;
					memcpy(solConfig, config, sizeof solConfig);

				}
				else if (area == minArea) {

					if (comp(config, solConfig) < 0)
						memcpy(solConfig, config, sizeof solConfig);

				}

			}

		}

	}

	fout << setprecision(1) << fixed << minArea / 2.0 << '\n';
	for (int i = 1; i <= n; ++i)
		if (solConfig[i] == 1)
			fout << 'I';
		else
			fout << 'V';

	fout << '\n';

	return 0;

}

//Trust me, I'm the Doctor!