Cod sursa(job #784775)

Utilizator danalex97Dan H Alexandru danalex97 Data 6 septembrie 2012 21:20:54
Problema Popandai Scor 12
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.52 kb
#include <fstream>
#include <iomanip>
#include <cmath>
using namespace std;

ifstream F("popandai.in");
ofstream G("popandai.out");

const int Nmax = 310;
const long long oo=1LL << 60;

typedef struct{int x,y;} Pair;

int N,K,Pnct;
Pair Point[Nmax];
int Banda[Nmax][Nmax];

long long Area=oo;
long long D[Nmax];

inline Pair make_pair(int x,int y)
{ Pair P; P.x=x; P.y=y; return P; }

inline void swamp(Pair& x,Pair& y)
{ swap(x.x,y.x);swap(x.y,y.y); }

inline int Sign (const Pair& P1, const Pair& P2, const Pair& P3)
{ return (P1.x*P2.y+P2.x*P3.y+P3.x*P1.y-P1.x*P3.y-P2.x*P1.y-P3.x*P2.y)<0 ? -1 : +1; }

inline int Mod (int x)
{ return (x<0?-x:x); }

inline int Aria (Pair P1,Pair P2,Pair P3)
{ return Mod(P1.x*P2.y+P2.x*P3.y+P3.x*P1.y-P1.x*P3.y-P2.x*P1.y-P3.x*P2.y); }

int Ec(Pair A,Pair B,Pair C)
{
	int a= A.y - B.y;
	int b= B.x - A.x;
	int c= -A.y * B.x + B.y * A.x ;
	int Val = C.x*a+C.y*b+c;
	Val = Val > 1 ? 1 : Val;
	Val = Val < -1 ? -1 : Val;
	return Val;
}

int Count(Pair A,Pair B,Pair C,int a,int b,int c)
{
	if ( A.x>B.x ) swamp(A,B),swap(a,b);
	if ( A.x>C.x ) swamp(A,C),swap(a,c);
	if ( B.x>C.x ) swamp(B,C),swap(b,c);
	
	if ( Ec(A,C,B)==1 ) 
		return Banda[a][b]+Banda[a][c]-Banda[a][c];
	return -Banda[a][b]-Banda[b][c]+Banda[a][c]-1;
}

int main()
{
	F>>N>>K;
	for (int i=1;i<=N;++i)
		F>>Point[i].x>>Point[i].y;
	Point[N+1]=make_pair(Point[1].x,Point[1].y);
	
	for (int i=1;i<=N;++i)
		for (int j=1;j<=N;++j)
			if ( i!=j )
				for (int k=1;k<=N;++k)
					if ( k!=i && k!=j && Point[k].x >= Point[i].x && Point[k].x <= Point[j].x )
						if ( Ec(Point[i],Point[j],Point[k]) == -1 ) ++Banda[i][j];
	
	for (int i=1;i<N;++i)
		for (int j=i+1;j<=N;++j)
		{
			Pnct=0;
			for (int k=0;k<=N+1;++k) D[k]=oo;
			for (int k=1;k<=N;++k)
				if ( k!=i && k!=j && Sign(Point[i],Point[j],Point[k])==-1 ) 
				{
					int Pl=Count(Point[i],Point[j],Point[k],i,j,k);
					int Ar=Aria(Point[i],Point[j],Point[k]);
					if ( Ar<D[Pl] ) D[Pl]=Ar;
				}
			for (int k=N; k>=0; --k)
                D[k]=min(D[k],D[k+1]);
            for (int k=1; k<=N; ++k)
                if (k!=i && k!=j && Sign(Point[i],Point[j],Point[k])==1)
                {
                    int c=Count(Point[i],Point[j],Point[k],i,j,k);
                    int s=K-c;
                    if ( s<0 ) s=K;
                    if ( D[s]==oo ) continue;
                    Area=min(Area,Aria(Point[i],Point[j],Point[k])+D[s]);
                }
		}
	
	G << fixed << setprecision(1) << (1.0*Area)/2 << '\n';
}