Cod sursa(job #1258971)

Utilizator CostanMiriamCostan Miriam CostanMiriam Data 9 noiembrie 2014 16:38:35
Problema Popandai Scor 88
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.88 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
#define inf 1<<29;

using namespace std;

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

int n,p,i,j,k,sol,d[310][310],a,b,c;
double up[310],dn[310],arie;

struct data {
    int x;
    int y;
}v[310];

bool cmp (const data &a, const data &b) {
    return (a.x!=b.x?a.x<b.x:a.y<b.y);
}

int det ( int i, int j, int k) {
    return 1LL*(v[j].x-v[i].x)*(v[k].y-v[i].y) - 1LL*(v[k].x-v[i].x)*(v[j].y-v[i].y);
}

int main () {

    fin>>n>>p;

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

    sort (v+1,v+n+1,cmp);

    for (i=1;i<n;i++)
        for (j=i+1;j<n;j++)
            for (k=j+1;k<=n;k++)
                if (det(i,k,j)<0){
                    d[i][k]++;
                    d[k][i]++;
                }

    arie=inf;

    for (i=1;i<n;i++)
        for (j=i+1;j<=n;j++) {
            for (k=0;k<=n;k++)
                up[k]=dn[k]=inf;
            for (k=1;k<=n;k++) {
                if (i==k || j==k)
                    continue;
                a=min(min(i,j),k);
                c=max(max(i,j),k);
                b=i;
                if (b==a||b==c) {
                    b=j;
                    if (b==a||b==c)
                        b=k;
                }
                sol=d[a][b]+d[b][c]-d[a][c];
                if (sol<0)
                   sol=(sol*(-1))-1;
                if (det(i,j,k)>0)
                    up[sol]=min(up[sol],1.0*det(i,j,k)/2.0);
                else
                    dn[sol]=min(dn[sol],-1.0*det(i,j,k)/2.0);
            }
            for(k=n-1;k>=0;k--) {
                up[k]=min(up[k],up[k+1]);
                dn[k]=min(dn[k],dn[k+1]);
            }
            for (k=0;k<=p;k++)
                arie=min(arie,up[k]+dn[p-k]);
        }
    fout<<setprecision(1)<<fixed<<arie<<"\n";


    return 0;
}