Cod sursa(job #1027445)

Utilizator scipianusFMI Ciprian Olariu scipianus Data 12 noiembrie 2013 19:51:06
Problema Popandai Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.67 kb
#include <fstream>
#include <cmath>
#include <algorithm>
#include <cstdio>
#define INF 1000000000.0
using namespace std;
int n, K, nr[310][310];
struct Punct{double x, y;};
Punct P[310];
double best[310], sol = INF;

inline bool Sortare(Punct A, Punct B)
{
	if(A.x == B.x)
		return A.y > B.y;
	return A.x < B.x;
}

inline void Citire()
{
	int i;
	ifstream fin("popandai.in");
	fin >> n >> K;
	for(i = 1; i <= n; ++i)
		fin >> P[i].x >> P[i].y;
	sort(P + 1, P + n + 1, Sortare);
	fin.close();
}

inline double Det(Punct A, Punct B, Punct C)
{
	return 0.5 * ( A.x * B.y + B.x * C.y + C.x * A.y - A.y * B.x - B.y * C.x - C.y * A.x);
}

inline void Preprocesare()
{
	int i, j, k;
	for(i = 1; i <= n; ++i)
	{
		for(j = i + 1; j <= n; ++j)
		{
			for(k = 1; k < j; ++k)
			{
				if(P[k].x >= min(P[i].x, P[j].x) && P[k].x < max(P[i].x, P[j].x))
				{
					if(Det(P[i], P[j], P[k]) < 0.0)
						nr[i][j]++;
					// nr[i][j] = cate puncte sunt sub segmentul [ P[i], P[j] )
				}
			}
		}
	}
}

inline int Count(int i,int j,int k)
{
	// calculeaza cate puncte sunt in interiorul triunghiului
	// format din P[i], P[j], P[k]
	int a, b, c;
	if(k < i)
	{
		a = k;
		b = i;
		c = j;
	}
	else
	{
		a = i;
		if(k < j)
		{
			b = k;
			c = j;
		}
		else
		{
			b = j;
			c = k;
		}
	}
	if(Det(P[a], P[c], P[b]) > 0.0)
		return nr[a][b] + nr[b][c] - nr[a][c];
	return nr[a][c] - nr[a][b] - nr[b][c] - 1;
}

inline void Rezolvare()
{
	int i, j, k, vizuine;
	for(i = 1; i <= n; ++i)
	{
		for(j = i + 1; j <= n; ++j)
		{
			for(k = 0; k <= n; ++k)
				best[k] = INF;
			// best[nr] = aria minima a unui triunghi facut de 
			// P[i], P[j] si un punct din stanga dreptei (P[i], P[j])
			// care are in interior cel putin nr puncte
			for(k = 1; k <= n; ++k)
			{
				if(Det(P[i], P[j], P[k]) < 0.0)
				{
					vizuine = Count(i, j, k);
					best[vizuine] = min(best[vizuine], fabs(Det(P[i], P[j], P[k])));
				}
			}
			for(k = n - 1; k >= 0; --k)
				best[k] = min(best[k], best[k + 1]);
			// iau punctele din partea dreapta si vad de ce fel de triunghi
			// (cu cati popandai minim) am nevoie din partea dreapta
			// pentru a face patrulater cu cel putin K puncte
			for(k = 1; k <= n; ++k)
			{
				if(Det(P[i], P[j], P[k]) > 0.0)
				{
					vizuine = Count(i, j, k);
					if(vizuine <= K)
						sol = min(sol, Det(P[i], P[j], P[k]) + best[K - vizuine]);
					else
						sol = min(sol, Det(P[i], P[j], P[k]) + best[0]);
				}
			}
		}
	}
}

inline void Afisare()
{
	freopen("popandai.out", "w", stdout);
	printf("%.1lf\n", sol);
}

int main()
{
	Citire();
	Preprocesare();
	Rezolvare();
	Afisare();
	return 0;
}