Cod sursa(job #780709)

Utilizator tzipleatudTudor Tiplea tzipleatud Data 21 august 2012 00:33:24
Problema Popandai Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.25 kb
#include <fstream>
#include <cstring>
#include <iomanip>
#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;
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 bool Under (const PI& P1, const PI& P2, const PI& P3)
{
    if (Sign(P1,P2,P3)==1) return 1;
    return (min(P1.x,P2.x)<=P3.x && P3.x<=max(P1.x,P2.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 (S<0?-S:S);
}

inline int Count (int A, int B, int C)
{
    if (V[A].x>V[B].x) swap(A,B);
    if (V[A].x>V[C].x) swap(A,C);
    if (V[B].x>V[C].x) swap(B,C);

    if (Sign(V[A],V[B],V[C])==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;

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

    for (i=1; i<=N; i++)
        for (j=i+1; j<=N; j++)
        {
            for (k=N; k>=0; k--)
                D[k]=INF;

            for (k=1; k<=N; k++)
                if (k!=i && k!=j && Sign(V[i],V[j],V[k])==1)
                {
                    int 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])==0)
                {
                    int c=Count(i,j,k);
                    int s=max(0,K-c);
                    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;
}