Cod sursa(job #2132389)

Utilizator MiricaMateiMirica Matei MiricaMatei Data 15 februarie 2018 18:52:26
Problema Popandai Scor 12
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.86 kb
#include <cstdio>
#include <algorithm>

using namespace std;

struct Punct {
  int x, y;

  bool operator < (const Punct& other) const {
    if (x == other.x)
      return y < other.y;
    return x < other.x;
  }
}v[305];

int r[5];
int p[5][305][305];

int myAbs(int x) {
  return x < 0 ? -x : x;
}

int area(Punct a, Punct b, Punct c) {
  int ans(a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y));
  return ans;
}

int sens(Punct a, Punct b, Punct c) {
  int ans = area(a, b, c);
  return ans > 0;
}

int in(int i, int j, int k) {
  r[1] = i;
  r[2] = j;
  r[3] = k;
  sort(r + 1, r + 4);
  i = r[1];
  j = r[3];
  k = r[2];
  int s = sens(v[i], v[j], v[k]) ^ 1;
  int ans = p[s][i][k] - p[s][i][j] - p[s][j][k];
  return ans > 0 ? ans : -ans;
}

int mina[5][305];

int main() {
  freopen("popandai.in", "r", stdin);
  freopen("popandai.out", "w", stdout);

  int n, m;
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; ++i)
    scanf("%d%d", &v[i].x, &v[i].y);
  sort(v + 1, v + n + 1);
  for (int i = 1; i <= n; ++i)
    for (int j = i + 1; j <= n; ++j)
      for (int k = i + 1; k < j; ++k)
        p[sens(v[i], v[j], v[k])][i][j]++;
  int ans = 1000000000;
  for (int i = 1; i <= n; ++i)
    for (int j = i + 1; j <= n; ++j) {
      for (int x = 0; x <= n; ++x)
        mina[0][x] = mina[1][x] = 1000000000;
      for (int k = 1; k <= n; ++k)
        if (k != i && k != j)
          mina[sens(v[i], v[j], v[k])][in(i, j, k)] = min(mina[sens(v[i], v[j], v[k])][in(i, j, k)], myAbs(area(v[i], v[j], v[k])));
      for (int k = n - 1; k >= 0; --k) {
        mina[0][k] = min(mina[0][k + 1], mina[0][k]);
        mina[1][k] = min(mina[1][k + 1], mina[1][k]);
      }
      for (int k = 0; k <= m; ++k)
        ans = min(ans, mina[0][k] + mina[1][m - k]);
    }

  printf("%.1f\n", 1. * ans / 2);
  return 0;
}