Cod sursa(job #163093)

Utilizator devilkindSavin Tiberiu devilkind Data 21 martie 2008 13:20:55
Problema Popandai Scor 32
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.07 kb
#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>

using namespace std;

struct point{long int x,y;};

#define NMAX 302
#define INF 0x3f3f3f3f
#define pb push_back
#define ss second
#define ff first
#define mp make_pair

long int n,K;
point pct[NMAX];
long int a[NMAX][NMAX];
double s[NMAX],d[NMAX];
long int col[NMAX];

inline double det(point P1, point P2, point P3)
{
	return P1.x*P2.y + P2.x*P3.y + P3.x*P1.y - P1.x*P3.y - P3.x*P2.y - P2.x*P1.y;
}

inline double ab(double x)
{
	if (x>0) return x;
	return -x;
}

long int query(long int x, long int y, long int z)
{
	long int s,sol;
	long int P1,P2,P3;
        vector< pair<int,int> > v;

        v.clear();
        
        v.pb( mp(pct[x].x,x) );
        v.pb( mp(pct[y].x,y) );
        v.pb( mp(pct[z].x,z) );

        sort(v.begin(),v.end());
        P1=v[0].ss;
        P2=v[1].ss;
        P3=v[2].ss;

        point P;

        if ( det(pct[P1],pct[P3],pct[P2])<0 ) s=-1;
		else s=1;
	
	sol=(a[P1][P2]+a[P2][P3]-a[P1][P3])*s;
        if (s==-1) sol=sol-1;
        if (col[P2]!=INF) sol=sol-1;
        if ( (s==1)&&(col[P2]!=INF) )
                        {
                        P.x=pct[P2].x;
                        P.y=col[P2];
                        if (det(pct[P1],pct[P3],P)>0) sol++;
                        }
	return sol;
}

int main()
{
	freopen("popandai.in","r",stdin);
	freopen("popandai.out","w",stdout);

	scanf("%ld %ld",&n,&K);

	long int i,j,k;

	for (i=1;i<=n;i++)
		scanf("%ld %ld",&pct[i].x,&pct[i].y);

        for (i=1;i<=n;i++)
                col[i]=INF;

	for (i=1;i<=n;i++)
		for (j=1;j<=n;j++)
		{
			if (i==j) continue;
			a[i][j]=0;
			for (k=1;k<=n;k++)
			{
				if (k==i) continue;
				if (k==j) continue;
				if ( ( det(pct[i],pct[j],pct[k])<0 )&&(pct[k].x>min(pct[j].x,pct[i].x)) && (pct[k].x<max(pct[j].x,pct[i].x) ) ) a[i][j]++;

                                if (pct[k].x==pct[i].x)
                                        if (pct[k].y<pct[i].y)
                                                col[i]=pct[k].y;
                                                        else col[k]=pct[i].y;

                                if (pct[k].x==pct[j].x)
                                        if (pct[k].y<pct[j].y)
                                                col[j]=pct[k].y;
                                                        else col[k]=pct[j].y;
			}
		}

	double ar=INF;

	for (i=1;i<=n;i++)
		for (j=i+1;j<=n;j++)
		{
			for (k=0;k<=n;k++)
			{
				s[k]=INF;
				d[k]=INF;
			}

			for (k=1;k<=n;k++)
			{
				if (k==i) continue;
				if (k==j) continue;
				
				if ( det(pct[i],pct[j],pct[k])<0 ) s[ query(i,j,k) ] = ab( det(pct[i],pct[j],pct[k])/2 );			
					else d[ query(i,j,k) ] = ab( det(pct[i],pct[j],pct[k])/2 );
			}

                        for (k=n-1;k>=0;k--)
                                {
                                s[k]=min(s[k],s[k+1]);
                                d[k]=min(d[k],d[k+1]);
                                }

			for (k=1;k<=n;k++)
			{
				if ( s[k]+d[K-k]<ar ) ar=s[k]+d[K-k];
				if ( d[k]+s[K-k]<ar ) ar=d[k]+s[K-k];
			}
		}

	printf("%.2lf",ar);
	return 0;
}