Cod sursa(job #3181127)

Utilizator emazareMazare Emanuel emazare Data 6 decembrie 2023 15:24:23
Problema Popandai Scor 28
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.44 kb
#include <fstream>
#include <algorithm>
#include <climits>

using namespace std;

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

struct punct{
    long long x;
    long long y;
} p[305];
long long ctr[305][305],pmin[305];

const long long INF = LLONG_MAX;
struct info_punct{
    long long area;
    long long cnt;
} pct1[305],pct2[305];

bool cmp(punct a, punct b){
    if(a.x == b.x)
        return(a.y<b.y);
    return(a.x<b.x);
}
bool cmp1(info_punct a, info_punct b){
    if(a.cnt == b.cnt)
        return(a.area<b.area);
    return(a.cnt<b.cnt);
}
long long pos(punct a, punct b, punct c){
    long long r = (c.y-a.y)*(b.x-a.x)-(c.x-a.x)*(b.y-a.y);
    if(r == 0 && ((a.x<=c.x && c.x<=b.x) || (b.x<=c.x && c.x<=a.x)))
        return 2;
    if(r>0)
        return 1;
    return 0;
}
bool check(punct a, punct b, punct g){
    if(a.x == b.x)
        return 0;
    punct c,d;
    c.x = a.x; d.x = b.x; c.y = d.y = 0;
    if(b.y == 0 && pos(b,a,g) == 1 && pos(a,c,g)!=0)
        return 1;
    if(a.y == 0 && pos(d,b,g) == 1 && pos(b,a,g)!=0)
        return 1;
    if(pos(d,b,g) == 1 && pos(b,a,g) == 1 && pos(a,c,g)!=0)
        return 1;
    return 0;
}
info_punct cxnt(long long i, long long j, long long k){
    info_punct str;
    long long v[3] = {i,j,k};
    sort(v,v+3);
    if(p[v[0]].x == p[v[1]].x){
        str.cnt = ctr[v[1]][v[2]]-ctr[v[0]][v[2]]-1;
        str.area = (p[v[1]].y+p[v[2]].y)*(p[v[2]].x-p[v[1]].x)-(p[v[0]].y+p[v[2]].y)*(p[v[2]].x-p[v[0]].x);
        return str;
    }
    str.cnt = abs(ctr[v[0]][v[1]]+ctr[v[1]][v[2]]-ctr[v[0]][v[2]]);
    str.area = abs((p[v[0]].y+p[v[1]].y)*(p[v[1]].x-p[v[0]].x)+(p[v[1]].y+p[v[2]].y)*(p[v[2]].x-p[v[1]].x)-(p[v[0]].y+p[v[2]].y)*(p[v[2]].x-p[v[0]].x));
    return str;
}

int main()
{
    long long n,k,i,j,l,r,nr1,nr2,amin = INF;
    fin >> n >> k;
    for(i=1;i<=n;i++)
        fin >> p[i].x >> p[i].y;
    sort(p+1,p+n+1,cmp);
    for(i=1;i<=n;i++){
        for(j=i+1;j<=n;j++){
            for(l=i+1;l<j;l++){
                if(check(p[i],p[j],p[l]))
                    ctr[i][j]++;
            }
            if(i>1 && check(p[i],p[j],p[i-1]))
                ctr[i][j]++;
        }
    }
    for(i=1;i<=n;i++){
        for(j=i+1;j<=n;j++){
            nr1 = nr2 = 0;
            for(l=1;l<=n;l++){
                if(l!=i && l!=j){
                    if(pos(p[i],p[j],p[l]) == 1){
                        info_punct str = cxnt(i,j,l);
                        pct1[++nr1].area = str.area;
                        pct1[nr1].cnt = str.cnt;
                    }
                    else{
                        info_punct str = cxnt(i,j,l);
                        pct2[++nr2].area = str.area;
                        pct2[nr2].cnt = str.cnt;
                    }
                }
            }
            sort(pct1+1,pct1+nr1+1,cmp1);
            sort(pct2+1,pct2+nr2+1,cmp1);
            pmin[nr2] = pct2[nr2].area;
            for(l=nr2-1;l>0;l--)
                pmin[l] = min(pmin[l+1],pct2[l].area);
            r = nr2+1;
            for(l=1;l<=nr1;l++){
                while(r>1 && pct1[l].cnt+pct2[r-1].cnt>=k)
                    r--;
                if(r<=nr2)
                    amin = min(amin,pmin[r]+pct1[l].area);
            }
        }
    }
    if(amin%2 == 0){
        amin/=2;
        fout << amin << ".0";
    }
    else{
        amin/=2;
        fout << amin << ".5";
    }
    return 0;
}