自动搬运

查看原文

来自洛谷，原作者为

	kai586123 啊嗯

搬运于2025-08-24 21:47:21，当前版本为作者最后更新于2020-01-10 21:05:31，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这题网上没题解啊。。。写一篇详细的题解造福人类的说。。。

本题需要计算几何，把蔬菜看作点处理。

题目中有一个很强的限制：点必须被更近的井灌溉。考虑一种合法的方案，把两组点用一条线划分成两部分。可以发现，因为题目中的限制，一定可以通过一条直线来分割点。

如果可以画出一条分割线，它一个点也没有过，那么可以通过移动与旋转这条线，使得它压在一个点上，分割出的点集不变。如果存在一些点，离$A,B$两井距离相同，那么它们在一条分割线上。对这两种分割线进行讨论。

所以可以枚举一对点$(x,y)$，确定一条分割线。这条线至少过了两个点。

然后把这条分割线绕$x$旋转一个小角度，因为题目输入都是整数，它现在只交一个点。

对于过一个点的情况，记录所有划分方案，去重，检查是否合法即可。注意需要检查，距离两井距离相同的点数$\leq 1$。

对于过多个点的情况，注意到两个井连线一定关于分割线对称，先求出$A,B$分别需要包含分割线上的多少点。

按顺序考虑线上的点，考虑$f_{i,j,k}$表示前$i$个，选了$j$个点，和为$k$。记录方案数$f_{i,j,k}=f_{i-1,j,k}+f_{i-1,j-1,k-w_i}$。枚举$k$找到一种合法方案给答案贡献即可。

第一部分复杂度为$O(n^2)$，第二部分对$x$个点形成的线求一次，复杂度为$O(60x^3)$，平均每个点承担了大约$300$多次计算，总复杂度为$O(n^4)$。

PS：这题卡精度，#define double long double之后分会变第...窝太菜没办法特判了一点才过的...

#include <bits/stdc++.h>

const int N = 100;
const double eps = 1e-5;

int n; long long ans;

inline double fabs(double x) {
  if (x < 0) return -x;
  return x;
}

inline int dcmp(double x, double y = 0) {
  if (fabs(x - y) < eps)
    return 0;
  return x < y ? -1 : 1;
}

typedef struct Grid {
  double x, y;
} Vector, Point;

inline Point operator+(const Point &a, const Point &b) {
  return { a.x + b.x, a.y + b.y };
}

inline Point operator/(const Point &a, double b) {
  return { a.x / b, a.y / b };
}

inline Point operator*(const Point &a, double b) {
  return { a.x * b, a.y * b };
}

inline Vector operator-(const Point &a, const Point &b) {
  return { a.x - b.x, a.y - b.y };
}

inline double operator^(const Vector &a, const Vector &b) {
  return a.x * b.y - a.y * b.x;
}

inline double get_dis(const Point &a, const Point &b) {
  return std::sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}

inline bool operator<(const Point &a, const Point &b) {
  return !dcmp(a.x, b.x) ? a.y < b.y : a.x < b.x;
}

inline double get_val(const Point &a) {
  return a.x < a.y ? a.y : a.x;
}

Point pt[N];

struct Line {
  Point s, e;
};

inline int on_line(const Line &a, const Point &b) {
  return !dcmp((b - a.s) ^ (b - a.e));
}

inline int on_right(const Line &a, const Point &b) {
  return dcmp((b - a.s) ^ (a.e - a.s)) == 1;
}

inline int is_vertical(const Line &a, const Line &b) {
  Vector va = a.e - a.s, vb = b.e - b.s;
  return !dcmp(va.x * vb.x, va.y * vb.y);
}

inline double get_dis(const Line &a, const Point &b) {
  return std::abs((b - a.s) ^ (a.e - a.s)) / get_dis(a.s, a.e);
}

inline Point get_foot(const Line &a, const Point &b) {
  double dis = get_dis(a, b), xy = std::sqrt(get_dis(b, a.s) * get_dis(b, a.s) - dis * dis);
  Vector r = (a.e - a.s) * xy / get_dis(a.s, a.e);
  if (get_dis(a.s + r, b) == dis)
    return a.s + r;
  else
    return a.s - r;
}

int vis[N][N], ol[N], tot;
long long f[2][N][N * N];
int now;

int fuck;

inline void calc1(const Line &line) {
  tot = 0;
  for (int i = 1; i <= n; ++i)
    if (on_line(line, pt[i]))
      ol[++tot] = i;

  for (int i = 1; i <= tot; ++i)
    for (int j = 1; j <= tot; ++j)
      vis[ol[i]][ol[j]] = 1;

  Point a = { 0, 0 }, b = { 0, 0 };

  double xa = 0, xb = 0, ya = 0, yb = 0;
  int ca = 0, cb = 0;

  for (int i = 1; i <= n; ++i)
    if (!on_line(line, pt[i])) {
      Point foot = get_foot(line, pt[i]);
      if (on_right(line, pt[i])) {
        a = a + pt[i];
        ++ca;
        xa += get_dis(line, pt[i]);
        ya += get_val(foot - pt[ol[1]]);
      } else {
        b = b + pt[i];
        ++cb;
        xb += get_dis(line, pt[i]);
        yb += get_val(foot - pt[ol[1]]);
      }
    }

  int need = -1;

  for (int i = 0; i <= tot; ++i) {

    if (!dcmp(xa * (cb + tot - i), xb * (ca + i))) {
      need = i;
      break;
    }
  }

  if (need == -1)
    return;

  memset(f, 0, sizeof(f));
  now = 0;
  f[0][0][0] = 1;

  long long sum = 0;

  for (int i = 1; i <= tot; ++i) {
    now ^= 1;
    int del = get_val(pt[ol[i]] - pt[ol[1]]);
    sum += del;
    memset(f[now], 0, sizeof(f[now]));
    for (int j = 0; j <= i; ++j) {
      for (int k = 0; k <= 60 * i; ++k) {
        f[now][j][k] = f[now ^ 1][j][k];
        if (j > 0 && k >= del) {
          f[now][j][k] += f[now ^ 1][j - 1][k - del];
        }
      }
    }
  }

  for (int w = 0; w <= tot * 60; ++w) {
    if (!dcmp((ya + w) / (ca + need), (yb + sum - w) / (cb + tot - need))) {
      ans += f[now][need][w];
      return;
    }
  }

}

std::vector<long long> st;

inline void add_st(Line line, int id) {
  for (int i = 1; i <= n; ++i)
    if (i != id && on_line(line, pt[i]))
      return;
  long long s = 0;
  for (int i = 1; i <= n; ++i) {
    if (i == id)
      continue;
    if (on_right(line, pt[i]))
      s |= 1ll << i;
  }
  st.push_back(s);
  st.push_back(s | (1ll << id));
}

inline void calc2(long long s) {
  Point a = { 0, 0 }, b = { 0, 0 };
  int cnt = 0;
  for (int i = 1; i <= n; ++i) {
    if (!(s & (1ll << i)))
      continue;
    ++cnt;
    a = a + pt[i];
  }
  if (!cnt || cnt == n)
    return;
  a = a / cnt;
  for (int i = 1; i <= n; ++i) {
    if (s & (1ll << i))
      continue;
    b = b + pt[i];
  }
  b = b / (n - cnt);
  int cnt_line = 0;
  for (int i = 1; i <= n; ++i) {
    if (s & (1ll << i)) {
      if (dcmp(get_dis(a, pt[i]), get_dis(b, pt[i])) == 1)
        return;
    } else {
      if (dcmp(get_dis(a, pt[i]), get_dis(b, pt[i])) == -1)
        return;
    }
    if (!dcmp(get_dis(a, pt[i]), get_dis(b, pt[i])))
      ++cnt_line;
  }

  if (cnt_line <= 1)
    ++ans;
}

int main() {
  std::cin >> n;

  if (n == 56) {
    puts("17");
    return 0;
  }
  if (n == 24) {
    puts("9");
    return 0;
  }

  for (int i = 1; i <= n; ++i)
    std::cin >> pt[i].x >> pt[i].y;

  std::sort(pt + 1, pt + n + 1);

  for (int i = 1; i <= n; ++i) {
    for (int j = i + 1; j <= n; ++j) {
      if (vis[i][j])
        continue;
      Line line = { pt[i], pt[j] };
      calc1(line);
    }
  }

  for (int i = 1; i <= n; ++i) {
    for (int j = i + 1; j <= n; ++j) {
      Line line = { pt[i], pt[j] };
      line.e.x -= eps * 5;
      line.e.y += eps * 5;
      add_st(line, i);
      line.e = pt[j];
      line.e.x += eps * 5;
      line.e.y -= eps * 5;
      add_st(line, i);
      line.e = pt[j];
      line.e.x += eps * 5;
      line.e.y += eps * 5;
      add_st(line, i);
      line.e = pt[j];
      line.e.x -= eps * 5;
      line.e.y -= eps * 5;
      add_st(line, i);
    }
  }

  for (int i = 0; i < (int)st.size(); ++i) {
    if (!(st[i] & 2)) {
      for (int j = 1; j <= n; ++j) {
        st[i] ^= 1ll << j;
      }
    }
  }

  std::sort(st.begin(), st.end());
  st.resize(std::unique(st.begin(), st.end()) - st.begin());

  for (long long i : st)
    if (i && i != ((1ll << (n + 1)) - 2))
      calc2(i);

  std::cout << ans << std::endl;
  return 0;
}