Cod sursa(job #342417)

Utilizator CezarMocanCezar Mocan CezarMocan Data 21 august 2009 17:07:41
Problema Popandai Scor 88
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.73 kb
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define maxn 302

using namespace std;

struct punct {
	int x, y, poz;
};

int sub[maxn][maxn];
int n, K, k, i, j, p1, p2, p3, z;
int sus[maxn], jos[maxn];
punct x[4], aux;
punct v[maxn], ver, t[maxn];
int sol, nr;
int aib[30100];

bool cmp(punct a, punct b) {
	if (a.x < b.x)
		return true;
	return false;
}

inline double tg(punct a, punct b) {
	return 1.0 * (a.y - b.y) / (1.0 * (a.x - b.x));
}

bool cmp2(punct a, punct b) {
	if (tg(a, v[i]) < tg(b, v[i]))
		return true;
	return false;
}

inline int arie(punct a, punct b, punct c) {
	return (1LL * a.x * b.y + 1LL * b.x * c.y + 1LL * c.x * a.y - 1LL * c.x * b.y - 1LL * b.x * a.y - 1LL * a.x * c.y);
}

inline int det(punct a, punct b, punct c) {
	if (arie(a, b, c) < 0)
		return -1;
	if (arie(a, b, c) > 0)
		return 1;
	return 0;
}

inline int min(int a, int b) {
	if (a < b)
		return a;
	return b;
}

int main() {
	freopen("popandai.in", "r", stdin);
	freopen("popandai.out", "w", stdout);
	
	scanf("%d%d", &n, &K);
	for (i = 1; i <= n; i++) {
		scanf("%d%d", &v[i].x, &v[i].y);
		v[i].x++; v[i].y++;
	}
	
	sort(v + 1, v + n + 1, cmp);
	for (i = 1; i <= n; i++)
		v[i].poz = i;
	
	for (i = 1; i <= n; i++)
		for (j = i + 1; j <= n; j++) {
			ver.x = v[i].x;
			ver.y = 0;
			for (k = i + 1; k < j; k++)
				if (det(v[i], v[j], ver) == det(v[i], v[j], v[k]))
					sub[i][j]++;
			sub[j][i] = sub[i][j];
		}
			
	sol = 2000000000;
	for (i = 1; i <= n; i++)
		for (j = i + 1; j <= n; j++) {
			
			for (k = 0; k <= n; k++) 
				sus[k] = jos[k] = 1000000000;
			
			for (k = 1; k <= n; k++) if (k != i && k != j) {
				
				if (v[i].x < v[k].x)	x[1] = v[i];
				else	x[1] = v[k];

				if (v[k].x > v[j].x)	x[3] = v[k];
				else 	x[3] = v[j];

				if (x[1].poz == v[i].poz)
					if (x[3].poz == v[k].poz)
						x[2] = v[j];
					else
						x[2] = v[k];
				else
					x[2] = v[i];
								
				p1 = x[1].poz; p2 = x[2].poz; p3 = x[3].poz;
				ver.x = x[1].x; ver.y = 0;
				int dver = det(x[1], x[3], ver);			
								
				if (det(x[1], x[3], x[2]) == dver) 
					z = sub[p1][p3] - sub[p1][p2] - sub[p2][p3] - 1;
				else
					z = sub[p1][p2] + sub[p2][p3] - sub[p1][p3];		
				
				int a = abs(arie(v[i], v[j], v[k]));
				if (det(v[i], v[j], v[k]) == 1)
					sus[z] = min(sus[z], a);				
				else
					jos[z] = min(jos[z], a);					
			}
			
			for (k = K - 1; k >= 0; k--) {
				sus[k] = min(sus[k], sus[k + 1]);
				jos[k] = min(jos[k], jos[k + 1]);
			}
			
			for (k = 0; k <= K; k++)
				sol = min(sol, sus[k] + jos[K - k]);
		}
		
	if (sol % 2 == 0)
		printf("%d.0", sol / 2);
	else
		printf("%d.5", sol / 2);
	
	return 0;
}