Cod sursa(job #2595845)

Utilizator alex_benescuAlex Ben alex_benescu Data 8 aprilie 2020 15:25:05
Problema Popandai Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.57 kb
#include<fstream>
#include<cstring>
#define N 310
#include<cmath>
#include<iomanip>
#include<algorithm>
#define x first
#define y second
#define inf 900000000
#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];
int det(int xa,int ya,int xb,int yb,int xc,int yc){
	long long D= 1LL*xa*yb+1LL*xb*yc+1LL*ya*xc-(1LL*xb*ya+1LL*xc*yb+1LL*xa*yc);
	return (int)D;
}
double area(int x){
	return ((double)x)/2.0;
}
int n,l,detu,q,w,e,nrp,und[N][N];
double poz[N],neg[N];
double best;
int main(){
	f>>n>>l;
	FOR(i,1,n)
	f>>v[i].x>>v[i].y;
	sort(v+1,v+n+1);
	FOR(i,1,n)
	FOR(j,i+1,n)
	FOR(k,j+1,n)
	{
		if(det(v[i].x,v[i].y,v[k].x,v[k].y,v[j].x,v[j].y)<0)
		{
			und[i][k]++;
			und[k][i]++;
		}
	}
	best=inf;
	FOR(i,1,n)
	FOR(j,i+1,n)
	{
		if(i==8&&j==5)
		{
			i++;
			i--;
		}
		FOR(k,0,n+1)
		poz[k]=neg[k]=inf;
		FOR(k,1,n)
		{
			if(k==i||k==j)
				continue;
			int a=i,b=k,c=j;

			if(b<a)
				swap(b,a);
			if(b>c)
				swap(b,c);
			detu=det(v[i].x,v[i].y,v[j].x,v[j].y,v[k].x,v[k].y);
			nrp=und[a][b]+und[b][c]-und[a][c];
			if(nrp<0)
				nrp=-nrp-1;
			if(detu>0)
			{
				if(area(detu)<poz[nrp])
					poz[nrp]=area(detu);
			}
			else
			{
				detu=-detu;
				if(area(detu)<neg[nrp])
					neg[nrp]=area(detu);
			}
		}
		for(int k=n;k>=0;--k)
		{
			poz[k]=min(poz[k],poz[k+1]);
			neg[k]=min(neg[k],neg[k+1]);
		}
		FOR(k,0,l)
		if(poz[k]+neg[l-k]<best)
			best=poz[k]+neg[l-k];
	}
	g<<fixed<<setprecision(1)<<best;
	return 0;
}