Cod sursa(job #2256596)

Utilizator RaduXD1Nicolae Radu RaduXD1 Data 8 octombrie 2018 20:53:59
Problema Popandai Scor 88
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.45 kb
#include<vector>
#include<fstream>
#include<algorithm>
#define f first
#define s second
#define INF 1000000000
using namespace std;
ifstream fin("popandai.in");
ofstream fout("popandai.out");
int n,k,i,j,h,a,b,c,sus[301][301],jos[301][301],up[301],down[301],punctaj,sum,val,sol;
int aux[4];
pair<int,int> v[301];

int arie(int x,int y,int x1,int y1,int x2,int y2)
{
    int aux=(x1-x)*(y2-y)-(x2-x)*(y1-y);
    if(aux<0)
        return -aux;
    return aux;
}

void calc(int i,int h, int j)
{
    int a,b,c,sum;
    a=v[i].s-v[j].s;
    b=v[j].f-v[i].f;
    c=v[i].f*(v[j].s-v[i].s)-v[i].s*(v[j].f-v[i].f);
    sum=v[h].f*a+v[h].s*b+c;
    if(sum>0)
        punctaj=jos[i][h]+jos[h][j]-jos[i][j];
    else
        punctaj=sus[i][h]+sus[h][j]-sus[i][j];
}

int main()
{
    fin>>n>>k;
    for(i=1;i<=n;i++)
        fin>>v[i].f>>v[i].s;
    sort(v+1, v+n+1);
    sol=INF;
    for(i=1;i<n;i++)
        for(j=i+1;j<=n;j++)
        {
            a=v[i].s-v[j].s;
            b=v[j].f-v[i].f;
            c=v[i].f*(v[j].s-v[i].s)-v[i].s*(v[j].f-v[i].f);
            for(h=1;h<=n;h++)
            {
                if(v[h].f*a+v[h].s*b+c<0&&v[h].f>=v[i].f&&v[h].f<=v[j].f)
                    jos[i][j]++;
                if(v[h].f*a+v[h].s*b+c>0&&v[h].f>=v[i].f&&v[h].f<=v[j].f)
                    sus[i][j]++;
            }
        }
    for(i=1;i<n;i++)
        for(j=i+1;j<=n;j++)
        {
            for(h=0;h<=300;h++)
                up[h]=INF,down[h]=INF;
            a=v[i].s-v[j].s;
            b=v[j].f-v[i].f;
            c=v[i].f*(v[j].s-v[i].s)-v[i].s*(v[j].f-v[i].f);
            for(h=1;h<=n;h++)
            {
                sum=v[h].f*a+v[h].s*b+c;
                if(sum!=0)
                {
                    aux[1]=i;aux[2]=j;aux[3]=h;
                    sort(aux+1, aux+4);
                    calc(aux[1],aux[2],aux[3]);
                    val=arie(v[i].f,v[i].s,v[j].f,v[j].s,v[h].f,v[h].s);
                    if(sum>0)
                        up[punctaj]=min(up[punctaj], val);
                    if(sum<0)
                        down[punctaj]=min(down[punctaj], val);
                }
            }
            for(h=299;h>=0;h--)
                up[h]=min(up[h],up[h+1]),down[h]=min(down[h],down[h+1]);
            for(h=0;h<=k;h++)
                sol=min(sol, up[h]+down[k-h]);
        }
    if(sol%2==0)
        fout<<sol/2<<".0";
    else
        fout<<sol/2<<".5";
    return 0;
}