Cod sursa(job #495062)

Utilizator indestructiblecont de teste indestructible Data 23 octombrie 2010 20:36:45
Problema Popandai Scor 72
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.02 kb
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <math.h>
#define NMAX 305
#define INF 2000000000
#define pb push_back
using namespace std;
struct pct {int x,y;};
pct A[NMAX];
int n,nr,B[NMAX][NMAX],C[NMAX],D[NMAX],r,s,H[4];
vector <int> E[NMAX],F[NMAX];
int arie1,arie2,arie,arie_b;
bool comp(pct a,pct b)
{
	if (a.x<b.x) return 1;
	if (a.x>b.x) return 0;
	if (a.y<b.y) return 1;
	return 0;
}
void read()
{
	scanf("%d%d",&n,&nr);
	int i;
	for (i=1; i<=n; i++)
		scanf("%d%d",&A[i].x,&A[i].y);
	sort(A+1,A+n+1,comp);
}
inline int under(int x,int y,int z)
{
	int a=A[y].y-A[x].y;
	int b=A[x].x-A[y].x;
	int c=A[y].x*A[x].y-A[x].x*A[y].y;
	double val=-(double)c/b-(double)a/b*A[z].x;
	return A[z].y<val;
}
void precompute()
{
	int i,j,k;
	for (i=1; i<=n; i++)
	{
		for (j=i+1; j<=n; j++)
		{
			for (k=i+1; k<j; k++)
				if (under(i,j,k))
					B[i][j]++;
		}
	}
}
inline int modul(int x)
{
	return x<0 ? -x : x;
}
inline int min(int x,int y)
{
	return x<y ? x : y;
}
void curata()
{
	int i;
	for (i=0; i<=n; i++)
		E[i].clear(),F[i].clear();
}
inline int area(pct a, pct b, pct c) 
{
	return modul(a.x * b.y + b.x * c.y + c.x * a.y - c.x * b.y - b.x * a.y - a.x * c.y);
}
void solve()
{
	int i,j,k,t,a,b,c,val,act,found,found1,ind;
	arie_b=INF;
	for (i=1; i<=n; i++)
		for (j=i+1; j<=n; j++)
		{
			a=A[j].y-A[i].y;
			b=A[i].x-A[j].x;
			c=A[j].x*A[i].y-A[i].x*A[j].y;
			r=s=0;
			for (k=1; k<=n; k++)
				if (k!=i && k!=j)
				{
					val=a*A[k].x+b*A[k].y+c;
					if (val<0)
						C[++r]=k;
					else
						D[++s]=k;
				}
			curata();
			
			for (k=1; k<=r; k++)
			{
				H[1]=i; H[2]=j; H[3]=C[k];
				sort(H+1,H+4);
				val=modul(B[H[1]][H[2]]+B[H[2]][H[3]]-B[H[1]][H[3]]);
				if (under(H[1],H[3],H[2])) val--;
				E[val].pb(C[k]);
			}
			for (k=1; k<=s; k++)
			{
				H[1]=i; H[2]=j; H[3]=D[k];
				sort(H+1,H+4);
				val=modul(B[H[1]][H[2]]+B[H[2]][H[3]]-B[H[1]][H[3]]);
				if (under(H[1],H[3],H[2])) val--;
				F[val].pb(D[k]);
			}
			
			arie2=INF; found=0; ind=nr;
			for (k=n-3; k>=nr; k--)
				if (F[k].size())
				{
					found=1;
					for (t=0; t<F[k].size(); t++)
					{
						act=F[k][t];
						arie1=area(A[i],A[j],A[act]);
						arie2=min(arie2,arie1);
					}
				}
				
			for (k=0; k<=n-3; k++)
			{
				arie=INF; found1=0;
				if (E[k].size())
				{
					found1=1;
					for (t=0; t<E[k].size(); t++)
					{
						act=E[k][t];
						arie1=area(A[i],A[j],A[act]);
						arie=min(arie,arie1);
					}
				}
				if (found && found1)
					arie_b=min(arie_b,arie+arie2);
				
				ind--;
				if (ind>=0)
				{
					if (F[ind].size())
					{
						found=1;
						for (t=0; t<F[ind].size(); t++)
						{
							act=F[ind][t];
							arie1=area(A[i],A[j],A[act]);
							arie2=min(arie2,arie1);
						}
					}
				}
			}
		}
}
int main()
{
	freopen("popandai.in","r",stdin);
	freopen("popandai.out","w",stdout);
	read();
	precompute();
	solve();
	printf("%.1lf\n",(double)arie_b/2);
	return 0;
}