Cod sursa(job #2016077)

Utilizator alexandra_udristoiuUdristoiu Alexandra Maria alexandra_udristoiu Data 28 august 2017 15:38:22
Problema Popandai Scor 24
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.33 kb
#include<fstream>
#include<algorithm>
#define x first
#define y second
using namespace std;
int k, n, i, j, ii, sol, s;
int d1[305], d2[305], a[305][305];
pair<int, int> v[305];
ifstream fin("popandai.in");
ofstream fout("popandai.out");
int det(pair<int, int> p1, pair<int, int> p2, pair<int, int> p3){
    return (p2.x - p1.x) * (p3.y - p1.y) - (p3.x - p1.x) * (p2.y - p1.y);
}
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 = -sol;
        sol--;
     }
     if(v[ w[1] ].x == v[ w[2] ].x && det(v[ w[2] ], v[ w[3] ], v[ w[1] ]) < 0){
        sol--;
     }
      if(v[ w[2] ].x == v[ w[3] ].x && det(v[ w[1] ], v[ w[2] ], v[ w[3] ]) < 0){
        sol--;
     }
     return sol;
}
int main(){
    fin>> n >> k;
    for(i = 1; i <= n; i++){
        fin>> v[i].x >> v[i].y;
    }
    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].x, v[j].x) <= v[ii].x && max(v[i].x, v[j].x) >= v[ii].x){
                    a[i][j]++;
                    a[j][i]++;
                }
            }
        }
    }
    sol = 2000000000;
    for(i = 1; i <= n; i++){
        for(j = i + 1; j <= n; j++){
            for(ii = 0; ii <= n; ii++){
                d1[ii] = d2[ii] = 2000000000;
            }
            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++){
                sol = min(sol, d1[ii] + d2[k - ii]);
            }
        }
    }
    if(sol % 2 == 1){
        fout<< sol / 2 <<".5\n";
    }
    else{
        fout<< sol / 2 <<".0\n";
    }
    return 0;
}