Cod sursa(job #2264267)

Utilizator Andrei_CotorAndrei Cotor Andrei_Cotor Data 19 octombrie 2018 22:41:39
Problema Popandai Scor 96
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.53 kb
#include<fstream>
#include<iomanip>
#include<algorithm>
#include<math.h>
#define x first
#define y second
using namespace std;
ifstream fi("popandai.in");
ofstream fo("popandai.out");
pair<long long,long long> A[305];
int n,k,S[305][305],i,j,ind;
long long rez,St[305],Dr[305];

bool checku(int i, int j, int k)
{
    long long val;
    if(A[j].x==A[i].x)
        return (A[k].x<A[i].x);
    else
        val=((A[j].y-A[i].y)*(A[k].x-A[i].x))/(A[j].x-A[i].x)+A[i].y;
    if(A[j].y<A[i].y)
        val--;
    return (val>=A[k].y);
}

bool checkst(int i, int j, int k)
{
    long long val;
    if(A[j].x==A[i].x)
        return (A[k].x<A[i].x);
    else
        val=((A[j].y-A[i].y)*(A[k].x-A[i].x))/(A[j].x-A[i].x)+A[i].y;
    if(A[j].y<A[i].y)
        return (val>=A[k].y);
    return (val<A[k].y);
}

int getpoints(int i, int j, int k)
{
    if(k<i)
    {
        swap(k,j);
        swap(i,j);
    }
    if(k<j)
        swap(k,j);
    if(checku(i,k,j))
        return (S[i][k]-1-S[i][j]-S[j][k]);
    return (S[i][j]+S[j][k]-S[i][k]);
}

long long modul(long long x)
{
    if(x<0)
        return -x;
    return x;
}

long long area(int i, int j, int k)
{
    return modul(1LL*(A[i].x-A[k].x)*(A[j].y-A[i].y)-1LL*(A[i].x-A[j].x)*(A[k].y-A[i].y));
}

int main()
{
    fi>>n>>k;
    for(i=1; i<=n; i++)
        fi>>A[i].x>>A[i].y;
    sort(A+1,A+n+1);
    for(i=1; i<n; i++)
        for(j=i+1; j<=n; j++)
            for(ind=i+1; ind<j; ind++)
                if(ind!=i && ind!=j && checku(i,j,ind))
                    S[i][j]++;
    rez=2000000000;
    for(i=1; i<n; i++)
        for(j=i+1; j<=n; j++)
        {
            for(ind=0; ind<=k; ind++)
                St[ind]=Dr[ind]=2000000000;
            for(ind=1; ind<=n; ind++)
            {
                if(ind==i || ind==j)
                    continue;
                if(checkst(i,j,ind))
                    St[min(getpoints(i,j,ind),k)]=min(St[min(getpoints(i,j,ind),k)],area(i,j,ind));
                else
                    Dr[min(getpoints(i,j,ind),k)]=min(Dr[min(getpoints(i,j,ind),k)],area(i,j,ind));
            }
            for(ind=k-1; ind>=0; ind--)
                St[ind]=min(St[ind],St[ind+1]);
            for(ind=k-1; ind>=0; ind--)
                Dr[ind]=min(Dr[ind],Dr[ind+1]);
            for(ind=0; ind<=k; ind++)
                rez=min(rez,St[ind]+Dr[k-ind]);
        }
    fo<<(rez/2);
    if(rez%2==1)
        fo<<".5";
    else
        fo<<".0";
    fi.close();
    fo.close();
    return 0;
}