Cod sursa(job #918149)

Utilizator apopeid13Apopeid Alejandro apopeid13 Data 18 martie 2013 17:42:52
Problema Popandai Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.09 kb
#include <fstream>
#include <cstring>
#include <iomanip>
#include <algorithm>

using namespace std;

#define int64 long long

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

#define x first
#define y second
typedef pair<int,int> Pair;

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

Pair V[Nmax];

int N,K,Banda[Nmax][Nmax];
int64 D[Nmax],Aria;

#define Formula (P1.x*P2.y+P2.x*P3.y+P3.x*P1.y-P1.x*P3.y-P2.x*P1.y-P3.x*P2.y)
#define Formula2 (Banda[A][B]+Banda[B][C]-Banda[A][C])
#define Formula3 (Banda[A][C]-Banda[A][B]-Banda[B][C]-1)

inline int Mod (int x) { return (x<0?-x:x);}
inline int Sign (const Pair& P1, const Pair& P2, const Pair& P3) { return (Formula<0?0:1); }
inline int Area (const Pair& P1, const Pair& P2, const Pair& P3) { return Mod(Formula); }
inline void Ord(int &A,int &B,int &C) { if (A>B) swap(A,B);	if (A>C) swap(A,C); if (B>C) swap(B,C);	}
inline int Count(int A, int B, int C) { Ord(A,B,C); return (Sign(V[A],V[C],V[B])==1) ? Formula2 : Formula3;  }

int main ()
{
    F >> N >> K;
    for (int i=1; i<=N; ++i)
        F >> V[i].x >> V[i].y;
    sort(V+1,V+N+1);

    for (int i=1; i<=N; ++i)
        for (int j=i+1; j<=N; ++j)
            for (int k=i+1; k<j; ++k)
                if (Sign(V[i],V[j],V[k])==0) ++Banda[i][j];

	Aria=oo;
    for (int i=1; i<=N; ++i)
        for (int j=i+1; j<=N; ++j)
        {
			int c,s;
			
            for (int k=0; k<=N+1; ++k) D[k]=oo;
            for (int k=1; k<=N; ++k)
                if ( k!=i && k!=j && Sign(V[i],V[j],V[k])==0 ) 
					c=Count(i,j,k), D[c]=min(D[c],1LL*Area(V[i],V[j],V[k]));
            
			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(V[i],V[j],V[k])==1 )
                {
                    c=Count(i,j,k);
                    s=K-c;
                    if (s<0) s=K;
                    if (D[s]==oo) continue;
                    Aria=min(Aria,Area(V[i],V[j],V[k])+D[s]);
                }
        }

    G << fixed << setprecision(1) << (1.0*Aria)/2 << '\n';
}