SRM503 Div1 Medium

500

村ごとに計算する。1番近い村が選ばれる確率、2番目に近い村が選ばれる確率、... を計算する。
これを間違わずに実装できる気がしないけれど、本番での正答率はそれなり。
ツラい。

double e_dist(int ax, int ay, int bx, int by)
{
  double x = (ax - bx);
  double y = (ay - by);
  return sqrt(x * x + y * y);
}

class KingdomXCitiesandVillages
{
public:
  double determineLength(vector <int> cX, vector <int> cY,
                         vector <int> vX, vector <int> vY)
  {
    const int C = cX.size();
    const int V = vX.size();

    const int F = 50 + 5;

    double f[F];
    f[0] = 1;
    for (int i = 1; i < F; ++i) {
      f[i] = f[i - 1] * i;
    }

    double ret = 0;

    for (int i = 0; i < V; ++i) {
      vector<double> ds;
      double mnC = 1e128;
      for (int j = 0; j < C; ++j) {
        mnC = min(mnC, e_dist(vX[i], vY[i], cX[j], cY[j]));
      }
      for (int j = 0; j < V; ++j) {
        if (i != j) ds.push_back(e_dist(vX[i], vY[i], vX[j], vY[j]));
      }
      sort(ds.begin(), ds.end());

      for (int j = 0; j < V - 1; ++j) {
        for (int k = 1; k <= (V - 1 - j); ++k) {
          int l = (V - 1) - (j + 1);
          double a = f[l] / f[l - (k - 1)];
          double b = f[k - 1];
          double c = a / b; // nCk
          double prob = c * f[k] * f[V - 1 - k] / f[V];
          double dist = min(mnC, ds[j]);
          ret += prob * dist;
        }
      }
      ret += mnC * f[V - 1] / f[V];
    }

    return ret;
  }