Cod sursa(job #495047)

Utilizator indestructiblecont de teste indestructible Data 23 octombrie 2010 19:55:44
Problema Popandai Scor 16
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.38 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,t;
vector <int> E[NMAX],F[NMAX];
double arie1,arie2,arie,arie_b,dist,dist2;
bool comp(pct a,pct b)
{
	return a.x<b.x;
}
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 double min(double x,double 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=t=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[++t]=k;
				}
			curata();
			
			for (k=1; k<=r; k++)
			{
				if (C[k]<i)
				{
					val=modul(B[C[k]][i]+B[i][j]-B[C[k]][j]);
					if (under(C[k],j,i)) val--;
				}
				if (C[k]>i && C[k]<j)
				{
					val=modul(B[i][C[k]]+B[C[k]][j]-B[i][j]);
					if (under(i,j,C[k])) val--;
				}
				if (C[k]>j)
				{
					val=modul(B[i][j]+B[j][C[k]]-B[i][C[k]]);
					if (under(i,C[k],j)) val--;
				}
				E[val].pb(C[k]);
			}
			
			for (k=1; k<=t; k++)
			{
				if (D[k]<i)
				{
					val=modul(B[D[k]][i]+B[i][j]-B[D[k]][j]);
					if (under(D[k],j,i)) val--;
				}
				if (D[k]>i && D[k]<j)
				{
					val=modul(B[i][D[k]]+B[D[k]][j]-B[i][j]);
					if (under(i,j,D[k])) val--;
				}
				if (D[k]>j)
				{
					val=modul(B[i][j]+B[j][D[k]]-B[i][D[k]]);
					if (under(i,D[k],j)) 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=(double)area(A[i],A[j],A[act])/2;
						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=(double)area(A[i],A[j],A[act])/2;
						arie=min(arie,arie1);
					}
				}
				if (found1 && found)
					arie_b=min(arie_b,arie+arie2);
				
				ind--;
				if (ind>=0)
				{
					if (F[ind].size())
					{
						found=1;
						for (t=0; t<F[k].size(); t++)
						{
							act=F[k][t];
							arie1=(double)area(A[i],A[j],A[act])/2;
							arie2=min(arie2,arie1);
						}
					}
				}
			}
		}
}
int main()
{
	freopen("popandai.in","r",stdin);
	freopen("popandai.out","w",stdout);
	read();
	precompute();
	solve();
	printf("%.1lf\n",arie_b);
	return 0;
}