Cod sursa(job #2255663)

Utilizator gavra_bogdanBogdan Gavra gavra_bogdan Data 7 octombrie 2018 13:23:08
Problema Popandai Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.46 kb
#include<bits/stdc++.h>
using namespace std;
int k, n, i, j, ii, sol, s;
int d1[305], d2[305], a[305][305];
pair<int, int> v[305];
int det(pair<int, int> p1, pair<int, int> p2, pair<int, int> p3)
{
    return (p2.first - p1.first) * (p3.second - p1.second) - (p3.first - p1.first) * (p2.second - p1.second);
}
int calc(int x, int y, int z)
{
     int w[4];
     w[1] = x;
     w[2] = y;
     w[3] = z;
     sort(w + 1, w + 4);
     int sol = a[ w[1] ][ w[2] ] + a[ w[2] ][ w[3] ] - a[ w[1] ][ w[3] ];
     if(sol < 0)
        sol=(-1)*sol-1;
     if(v[ w[1] ].first == v[ w[2] ].first && det(v[ w[2] ], v[ w[3] ], v[ w[1] ]) < 0)
        sol--;
            if(v[ w[2] ].first == v[ w[3] ].first && det(v[ w[1] ], v[ w[2] ], v[ w[3] ]) < 0)
        sol--;
     return sol;
}
int main()
{
    ifstream cin("popandai.in");
    ofstream cout("popandai.out");
    cin>> n >> k;
    for(i = 1; i <= n; i++)
        {
        cin>> v[i].first >> v[i].second;
    }
    sort(v + 1, v + n + 1);
    for(i = 1; i < n; i++)
    {
        for(j = i + 1; j <= n; j++)
        {
            for(ii = 1; ii <= n; ii++)
            {
                if(det(v[i], v[j], v[ii]) < 0 && min(v[i].first, v[j].first) <= v[ii].first && max(v[i].first, v[j].first) >= v[ii].first)
                {
                    a[i][j]++;
                    a[j][i]++;
                }
            }
        }
    }
    sol = INT_MAX;
    for(i = 1; i <= n; i++){
        for(j = i + 1; j <= n; j++){
            for(ii = 0; ii <= n; ii++){
                d1[ii] = d2[ii] = INT_MAX;
            }
            for(ii = 1; ii <= n; ii++){
                if(det(v[i], v[j], v[ii]) > 0){
                    s = calc(i, j, ii);
                    d1[s] = min(d1[s], det(v[i], v[j], v[ii]) );
                }
                if(det(v[i], v[j], v[ii]) < 0){
                    s = calc(i, j, ii);
                    d2[s] = min(d2[s], -det(v[i], v[j], v[ii]) );
                }
            }
            for(ii = n - 1; ii >= 0; ii--){
                d1[ii] = min(d1[ii], d1[ii + 1]);
                d2[ii] = min(d2[ii], d2[ii + 1]);
            }
            for(ii = 0; ii <= k; ii++){
                if(d1[ii] != INT_MAX && d2[k - ii] != INT_MAX)
                sol = min(sol, d1[ii] + d2[k - ii]);
            }
        }
    }
    if(sol % 2 == 1){
        cout<< sol / 2 <<".5\n";
    }
    else{
        cout<< sol / 2 <<".0\n";
    }
    return 0;
}