Nu aveti permisiuni pentru a descarca fisierul grader_test9.ok
Cod sursa(job #2016076)
Utilizator | Data | 28 august 2017 15:35:50 | |
---|---|---|---|
Problema | Popandai | Scor | 88 |
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 = 1000000000;
for(i = 1; i <= n; i++){
for(j = i + 1; j <= n; j++){
for(ii = 0; ii <= n; ii++){
d1[ii] = d2[ii] = 1000000000;
}
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;
}