Cod sursa(job #2414288)

Utilizator NicolaalexandraNicola Alexandra Mihaela Nicolaalexandra Data 24 aprilie 2019 14:13:55
Problema Popandai Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.33 kb
#include <fstream>
#include <algorithm>
#include <cstring>
#define DIM 310
#define INF 2000000000
using namespace std;

ifstream fin ("popandai.in");
ofstream fout ("popandai.out");

struct punct{
    int x,y;
};
punct v[DIM];
int d[DIM][DIM];
int n,k,i,j,t,x,a,b,c,nr,A,B,C;
long long sol,up[DIM],down[DIM];
inline void calcul_ecuatie (int X1, int Y1, int X2, int Y2, int &a, int &b, int &c){
    a = Y2-Y1;
    b = X1-X2;
    c = Y1*(X2-X1) - X1*(Y2-Y1);
}
inline int det (int a, int b, int c, int x, int y){
    return a*x + b*y + c;
}

int get_points (int A, int B, int C){ /// cate puncte am in triunghi
    /// A.x <= B.x <= C.x
    int a,b,c;
    calcul_ecuatie (v[A].x,v[A].y,v[C].x,v[C].y,a,b,c);
    if (det(a,b,c,v[B].x,v[B].y) < 0)
        return d[A][B] + d[B][C] - d[A][C];
    return d[A][C] - d[A][B] - d[B][C] - 1;
}
long long get_arie (int X1, int Y1, int X2, int Y2, int X3, int Y3){
    long long arie = 1LL*(X2-X1)*(Y3-Y1) - 1LL*(X3-X1)*(Y2-Y1);
    if (arie >= 0)
        return arie;
    return -arie;
}
bool cmp (punct a, punct b){
    if (a.x == b.x)
        return a.y < b.y;
    return a.x < b.x;
}
inline void init(){
    for (int i=0;i<=k;i++)
        up[i] = down[i] = INF;
}
int main (){

    fin>>n>>k;
    for (i=1;i<=n;i++)
        fin>>v[i].x>>v[i].y;

    sort (v+1,v+n+1,cmp);
    /// calculez pt fiecare segment determinat de 2 pucnte cate se gasesc sub el
    for (i=1;i<=n;i++){
        for (j=i+1;j<=n;j++){
            if (i == j)
                continue;
            calcul_ecuatie (v[i].x,v[i].y,v[j].x,v[j].y,a,b,c);
            nr = 0;
            for (t=1;t<=n;t++){
                if (t == i || t == j)
                    continue;
                if (v[t].x >= v[i].x && v[t].x <= v[j].x && det(a,b,c,v[t].x,v[t].y) > 0)
                    nr++;
            }
            d[i][j] = d[j][i] = nr;
        }}

    /*for (i=1;i<=n;i++){
        for (j=1;j<=n;j++)
            fout<<d[i][j]<<" ";
        fout<<"\n";
    }*/
    /// fixam o diagonala
    sol = 2000000000000000000LL;
    for (i=1;i<n;i++){
        for (j=i+1;j<=n;j++){
            /// vreau sa selectez un punct deasupra diagonalei fixate
            /// a.i. triunghil sa contina fix x puncte si sa fie de arie minima
            calcul_ecuatie (v[i].x,v[i].y,v[j].x,v[j].y,a,b,c);
            //memset (up,INF,sizeof(up));
            //memset (down,INF,sizeof(down));
            init();
            for (t=1;t<=n;t++){ /// puncte de deasupra
                if (t == i || t == j)
                    continue;

                /// sa vad daca e deaspura
                if (det(a,b,c,v[t].x,v[t].y) > 0)
                    continue;

                A = i, B = j, C = t;
                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);

                x = get_points (A,B,C);
                //if (up[x] != 0)
                    up[x] = min (up[x],get_arie(v[i].x,v[i].y,v[j].x,v[j].y,v[t].x,v[t].y));
                //else up[x] = get_arie(v[i].x,v[i].y,v[j].x,v[j].y,v[t].x,v[t].y);
            }

            for (t=1;t<=n;t++){ /// puncte de dedesubt
                if (t == i || t == j)
                    continue;

                /// sa vad daca e deaspura
                if (det(a,b,c,v[t].x,v[t].y) < 0)
                    continue;

                A = i, B = j, C = t;
                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);

                x = get_points (A,B,C); /// cate puncte am in interiorul triunghiului
                //if (down[x] != 0)
                    down[x] = min (down[x],get_arie(v[i].x,v[i].y,v[j].x,v[j].y,v[t].x,v[t].y));
                //else down[x] = get_arie(v[i].x,v[i].y,v[j].x,v[j].y,v[t].x,v[t].y);
            }


            for (x=k-1;x>=0;x--){
                up[x] = min (up[x],up[x+1]);
                down[x] = min (down[x],down[x+1]);
            }
            /// up[i], down[i] - aria minima a unui tringhi ce contne minim i puncte

            for (x=0;x<=k;x++)
                sol = min (sol,(long long)(up[x]+down[k-x]));

        }}

    fout<<sol/2;
    if (sol%2)
        fout<<".5";
    else fout<<".0";

    return 0;
}