Cod sursa(job #164806)

Utilizator sims_glAlexandru Simion sims_gl Data 24 martie 2008 20:48:36
Problema Popandai Scor 8
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.18 kb
#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

#define nm 310
#define xx first
#define yy second
#define inf 1000000000

int n, m, nr[nm][nm];
double sol = inf;
vector< pair<int, int> > v;

inline int abs(int x)
{
	if (x < 0)
		return -x;
	return x;
}

inline int det(int i, int j, int k)
{
	return v[i].xx * v[j].yy + v[j].xx * v[k].yy + v[k].xx * v[i].yy - v[i].xx * v[k].yy - v[j].xx * v[i].yy - v[k].xx * v[j].yy;
}

int cate(int i, int j, int k)
{
	int rez = 0;

	if (v[i].xx * v[j].yy - v[j].xx * v[i].yy > 0)
		rez += nr[i][j];
	else
		rez -= nr[i][j];

	if (v[j].xx * v[k].yy - v[k].xx * v[j].yy > 0)
		rez += nr[j][k];
	else
		rez -= nr[j][k];

	if (v[k].xx * v[i].yy - v[i].xx * v[k].yy > 0)
		rez += nr[k][i];
	else
		rez -= nr[k][i];

	return abs(rez);
}

double arie(int i, int j, int k)
{
	return 0.5 * abs(det(i, j, k));
}

int main()
{
	freopen("popandai.in", "r", stdin);
	freopen("popandai.out", "w", stdout);

	scanf("%d%d", &n, &m);

	for (int i = 1; i <= n; ++i) {
		int x, y;

		scanf("%d%d", &x, &y);
		v.push_back(make_pair(x, y));
	}

	sort(v.begin(), v.end());
/*
	for (int i = 0; i < n; ++i)
		printf("%d %d\n", v[i].xx, v[i].yy);
*/
	for (int i = 0; i < n; ++i)
		for (int j = i + 1; j < n; ++j) 
			if (v[i].xx != v[j].xx) if (i != j) {
				int a = v[j].yy - v[i].yy, b = v[i].xx - v[j].xx, c = v[i].yy - a * v[i].xx;

				for (int k = 0; k < n; ++k)
					if (k != i && k != j)
						if (a * v[k].xx + b * v[k].yy + c > 0)
							++nr[i][j];

				nr[j][i] = nr[i][j];
			}
/*
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j)
			printf("%d ", nr[i][j]);
		printf("\n");
	}
*/
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= n; ++j) if (i != j) {
			int a = v[j].yy - v[i].yy, b = v[i].xx - v[j].xx, c = v[i].yy - a * v[i].xx;
			double st = inf, dr = inf;

			for (int k = 1; k <= n; ++k)
				if (k != i && k != j) {
					int temp = cate(i, j, k);
					double area = arie(i, j, k);

					if (a * v[k].xx + b * v[k].yy + c < 0 && temp >= m && area < st)
						st = area;
					else if (a * v[k].xx + b * v[k].yy + c > 0 && temp >= m && area < dr)
						dr = area;
				}

			if (sol > st + dr)
				sol = st + dr;
		}

	printf("%.1lf\n", sol);

	return 0;
}