Cod sursa(job #780959)

Utilizator tzipleatudTudor Tiplea tzipleatud Data 22 august 2012 22:22:57
Problema Popandai Scor 88
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.14 kb
#include <fstream>
#include <cstring>
#include <iomanip>
#include <cassert>
#include <algorithm>
#define NM 310
#define x first
#define y second
#define INF 999999999

using namespace std;

ifstream f("popandai.in");
ofstream g("popandai.out");

typedef pair<int, int> PI;
PI V[NM];

int N,K,i,j,k,c,s;
int Points[NM][NM],D[NM],ANS=INF;

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

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

inline int Area (const PI& P1, const PI& P2, const PI& P3)
{
    int S=P1.x*P2.y+P2.x*P3.y+P3.x*P1.y-P1.x*P3.y-P2.x*P1.y-P3.x*P2.y;
    return Mod(S);
}

inline int Count (int A, int B, int C)
{
    if (A>B) swap(A,B);
    if (A>C) swap(A,C);
    if (B>C) swap(B,C);

    if (Sign(V[A],V[C],V[B])==1)
        return Points[A][B]+Points[B][C]-Points[A][C];

    return Points[A][C]-Points[A][B]-Points[B][C]-1;
}

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

    for (i=1; i<=N; i++)
        for (j=i+1; j<=N; j++)
        {
            for (k=i+1; k<j; k++)
                if (Sign(V[i],V[j],V[k])==0)
                    Points[i][j]++;
        }

    for (i=1; i<=N; i++)
        for (j=i+1; j<=N; j++)
        {
            for (k=0; k<=N+1; k++)
                D[k]=INF;
            for (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],Area(V[i],V[j],V[k]));
                }

            for (k=N; k>=0; k--)
                D[k]=min(D[k],D[k+1]);

            for (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;
                    ANS=min(ANS,Area(V[i],V[j],V[k])+D[s]);
                }
        }

    g << fixed << setprecision(1) << (1.0*ANS)/2 << '\n';
    f.close();
    g.close();
    return 0;
}