Cod sursa(job #1359709)

Utilizator nimicLeoveanu Mihaita Alexandru nimic Data 25 februarie 2015 01:16:17
Problema Popandai Scor 4
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.23 kb
#include<fstream>
#include<iomanip>
using namespace std;
ifstream in("popandai.in");
ofstream out("popandai.out");

struct punct{
	long long x, y;
};

const int nmax = 306, inf = 1000000000;
int n, k, poz[nmax];
punct v[nmax];
int vmagic[nmax][nmax];
double rasp = inf;

inline long long modul(long long x)
{
	if(x<0)
		return -x;
	else
		return x;
}

inline int aria(punct a, punct b, punct c)
{
    return modul(a.x * b.y + b.x * c.y + c.x * a.y - a.x * c.y - b.x * a.y - c.x * b.y);
}

inline int det(punct a,punct b,punct c)
{
    return (a.x - b.x) * (c.y - b.y) - (a.y - b.y) * (c.x - b.x);
}

bool esub(int i, int j, int h)
{
	int rlim = max(v[i].x, v[j].x), llim = min(v[i].x, v[j].x);
	int aux;

				if(v[i].x<v[j].x)
					aux = det(v[j], v[i], v[h]);
				else
					aux = det(v[i], v[j], v[h]);
				if(h!=i && h!=j && v[h].x<=rlim && v[h].x>llim && aux<=0)
					return 1;
				else
					return 0;
}

int main(){
	int player_unu=0;

	out<<setprecision(1)<<fixed;

	in>>n>>k;
	for(int i = 1; i<=n; i++)
	{
		in>>v[i].x>>v[i].y;
	}

	for(int i = 1; i<=n; i++)
	{
		for(int j = i + 1; j<=n; j++)
		{
			for(int h = 1; h<=n; h++)
			{
				vmagic[i][j] += esub(i, j, h);
			}

			vmagic[j][i] = vmagic[i][j];
		}
	}

	for(int i = 1; i<=n; i++)
	{
		for(int j = i + 1; j<=n; j++)
		{
			for(int h = 0; h<n; h++)
				poz[h] = inf;

			for(int h = 1; h<=n; h++)
			{
				int aux1;

				if(v[i].x<v[j].x)
					aux1 = det(v[j], v[i], v[h]);
				else
					aux1 = det(v[i], v[j], v[h]);

				if(h!=i && h!=j && aux1<=0)
				{
					int aux = modul(vmagic[i][j] - vmagic[h][j] - vmagic[h][i]) - esub(i, j, h);
					poz[aux] = min(poz[aux], aria(v[i], v[j], v[h]));
				}
			}

			for(int h = 1; h<=n; h++)
			{
				int aux1;

				if(v[i].x<v[j].x)
					aux1 = det(v[j], v[i], v[h]);
				else
					aux1 = det(v[i], v[j], v[h]);

				if(h!=i && h!=j && aux1>0)
				{
					int aux = k - modul(vmagic[i][j] - vmagic[h][j] - vmagic[h][i]) + esub(j, h, i) + esub(h, i , j);
					
					if(aux>=0)
					{
						if(poz[aux] + aria(v[i], v[j], v[h])<rasp)
							rasp = poz[aux] + aria(v[i], v[j], v[h]);
					}
				}
			}
		}
	}

	out<<rasp / 2<<'\n';

	return player_unu;
}