Cod sursa(job #1171874)

Utilizator Kira96Denis Mita Kira96 Data 16 aprilie 2014 15:16:23
Problema Popandai Scor 12
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.69 kb
#include<fstream>
#include<cstring>
#define N 310
#include<cmath>
#include<iomanip>
#include<algorithm>
#define x first
#define y second
#define inf 0x3f3f3f3f
#define FOR(a,b,c) for(int a=b;a<=c;a++)
using namespace std;
ifstream f("popandai.in");
ofstream g("popandai.out");
pair<int,int> v[N];
pair<pair<int,int> , int> a[N];
int det(int xa,int ya,int xb,int yb,int xc,int yc)
{
	return xa*yb+xb*yc+ya*xc-(xb*ya+xc*yb+xa*yc);
}
int n,l,detu,q,w,e,nrp,poz[N],neg[N],best,und[N][N];
int main ()
{
	f>>n>>l;
	FOR(i,1,n)
	f>>v[i].x>>v[i].y;
	
	FOR(i,1,n)
	FOR(j,1,i-1)
	{
		a[1].x.x=v[i].x;
		a[1].x.y=v[i].y;
		a[2].x.x=v[j].x;
		a[2].x.y=v[j].y;
		sort(a+1,a+3);
		FOR(k,1,n)
		{
			if(v[k].x>=a[1].x.x&&v[k].x<=a[2].x.x&&det(a[1].x.x,a[1].x.y,a[2].x.x,a[2].x.y,v[k].x,v[k].y)<0)
			{
				und[i][j]++;
				und[j][i]++;
			}
		}
	}
	best=inf;
	FOR(i,1,n)
	FOR(j,1,i-1)
	{
		if(i==8&&j==5)
		{
			i++;
			i--;
		}
		memset(poz,inf,sizeof(poz));
		memset(neg,inf,sizeof(neg));
		FOR(k,1,n)
		{
			a[1].x.x=v[i].x;
			a[1].x.y=v[i].y;
			a[2].x.x=v[j].x;
			a[2].x.y=v[j].y;
			a[3].x.x=v[k].x;
			a[3].x.y=v[k].y;
			a[1].y=i;
			a[2].y=j;
			a[3].y=k;
			
			sort(a+1,a+4);
			
			detu=det(a[1].x.x,a[1].x.y,a[2].x.x,a[2].x.y,a[3].x.x,a[3].x.y);
			q=a[1].y; w=a[2].y; e=a[3].y;
			if(detu<0)
			{
				detu=-detu;
				nrp=und[q][w]+und[w][e]-und[q][e];
				if(detu<neg[nrp])
					neg[nrp]=detu;
			}
			else
			if(detu>0)
			{
				nrp=und[q][e]-und[q][w]-und[e][w]-1;
				if(detu<poz[nrp])
					poz[nrp]=detu;
			}
		}
		FOR(k,0,l)
		if(poz[k]+neg[l-k]<best)
			best=poz[k]+neg[l-k];
	}
	g<<fixed<<setprecision(1)<<(double)best/2;
	return 0;
}