题目分析

方伯伯需要在 $n$ 个蔬菜位置中选择两个井的位置，并分配灌溉关系，满足以下条件：

1. 井必须位于其灌溉蔬菜的几何中心
2. 所有蔬菜必须被灌溉
3. 每口井至少灌溉一棵蔬菜
4. 蔬菜由距离更近的井灌溉（距离相等可任意）
5. 井不能重合，蔬菜位置互不相同

解题思路

通过枚举所有可能的划分直线，利用计算几何方法判断点的相对位置，然后使用动态规划统计满足几何中心约束的分配方案。

算法核心

1. 枚举基准直线：遍历所有点对确定候选划分
2. 点集分类：将点分为直线上、左侧、右侧三类
3. 几何约束验证：检查井位置是否满足中心条件
4. 动态规划计数：统计合法的点分配方案

完整代码

#include <algorithm>
#include <cstdio>
#include <vector>
#include <cmath>
#include <set>
using namespace std;

typedef pair<int, int> P;
const double eps = 1e-10;

int n, in1, in2;
vector<P> nd, qu[3];
vector<int> dt;
set<unsigned long long> ss, se;
unsigned long long MA, hs, hs1, res, dp[65][5000];

P operator*(const P &x, const P &y) {
    return P(x.first * y.first - x.second * y.second, x.first * y.second + x.second * y.first);
}

double gtln(double x, double y, double xx, double yy) {
    return sqrt((xx - x) * (xx - x) + (yy - y) * (yy - y));
}

P operator-(const P &x, const P &y) {
    return P(x.first - y.first, x.second - y.second);
}

int operator^(const P &x, const P &y) {
    return x.first * y.second - x.second * y.first;
}

int gtop(double x) {
    return x < -eps ? 2 : (x > eps ? 1 : 0);
}

int gcd(int x, int y) {
    return x % y ? gcd(y, x % y) : y;
}

void wk2() {
    int bas = qu[0].front().first;
    P x = qu[0].front(), y = (*++qu[0].begin()) - x;
    int tt0 = 0, tt1 = 0, tt2 = 0, tt3 = 0, tt4 = 0, g = 0;
    y.second = -y.second;
    dt.clear();

    for (vector<P>::iterator ite = qu[1].begin(); ite != qu[1].end(); ite++) {
        P nw = (*ite - x) * y;
        tt0 += nw.first, tt1 += nw.second;
    }

    for (vector<P>::iterator ite = qu[2].begin(); ite != qu[2].end(); ite++) {
        P nw = (*ite - x) * y;
        tt2 += nw.first, tt3 += nw.second;
    }

    for (vector<P>::iterator ite = qu[0].begin(); ite != qu[0].end(); ite++) {
        P nw = (*ite - x) * y;
        dt.push_back(nw.first);
        if (nw.first) g = gcd(g, nw.first);
    }

    int a = tt1 * (qu[2].size() + qu[0].size()) + tt3 * qu[1].size();
    int b = tt1 - tt3;
    if (a % b) return;
    
    int cn = a / b;
    if (cn < 0 || cn > qu[0].size()) return;

    for (vector<int>::iterator ite = dt.begin(); ite != dt.end(); ite++)
        tt4 += *ite, *ite /= g;

    a = (qu[1].size() + cn) * (tt2 + tt4) - (qu[2].size() + qu[0].size() - cn) * tt0;
    if (a % n) return;
    
    int tt = a / n;
    if (tt < 0 || tt > tt4 || tt % g) return;
    
    tt /= g;
    dp[0][0] = 1;

    for (vector<int>::iterator ite = dt.begin(); ite != dt.end(); ite++)
        for (int i = cn; i; i--)
            for (int j = tt; j >= *ite; j--)
                dp[i][j] += dp[i - 1][j - *ite];

    res += dp[cn][tt];

    for (int i = 0; i <= cn; i++)
        for (int j = 0; j <= tt; j++)
            dp[i][j] = 0;
}

void tst() {
    unsigned long long nw = hs1 & 1 ? hs1 : hs1 ^ MA;
    if (se.find(nw) != se.end()) return;
    se.insert(nw);

    if (qu[1].empty() || qu[2].empty()) return;

    double tt0 = 0, tt1 = 0, tt2 = 0, tt3 = 0;
    for (vector<P>::iterator ite = qu[1].begin(); ite != qu[1].end(); ite++)
        tt0 += ite->first, tt1 += ite->second;
    for (vector<P>::iterator ite = qu[2].begin(); ite != qu[2].end(); ite++)
        tt2 += ite->first, tt3 += ite->second;

    int cn = 0;
    tt0 /= qu[1].size();
    tt1 /= qu[1].size();
    tt2 /= qu[2].size();
    tt3 /= qu[2].size();

    if (fabs(tt0 - tt2) < eps && fabs(tt1 - tt3) < eps) return;

    for (vector<P>::iterator ite = qu[1].begin(); ite != qu[1].end(); ite++)
        switch (gtop(gtln(tt0, tt1, ite->first, ite->second) - gtln(tt2, tt3, ite->first, ite->second))) {
            case 0: cn++; break;
            case 1: return;
        }

    for (vector<P>::iterator ite = qu[2].begin(); ite != qu[2].end(); ite++)
        switch (gtop(gtln(tt2, tt3, ite->first, ite->second) - gtln(tt0, tt1, ite->first, ite->second))) {
            case 0: cn++; break;
            case 1: return;
        }

    if (cn < 2) res++;
}

void dfs(const P &x, const P &y) {
    hs = hs1 = 0;
    for (vector<P>::iterator ite = nd.begin(); ite != nd.end(); ite++) {
        hs <<= 1;
        hs1 <<= 1;
        switch (gtop(*ite - x ^ y - x)) {
            case 0: qu[0].push_back(*ite), hs ^= 1; break;
            case 1: qu[1].push_back(*ite), hs1 ^= 1; break;
            case 2: qu[2].push_back(*ite); break;
        }
    }

    unsigned long long nw = hs;
    if (ss.find(hs) == ss.end()) {
        ss.insert(hs);
        if (!qu[1].empty() && !qu[2].empty()) wk2();

        int sz = qu[0].size();
        for (vector<P>::iterator ite = qu[0].begin(); ite != qu[0].end(); ite++)
            qu[2].push_back(*ite);

        hs1 ^= nw & -nw, nw ^= nw & -nw;
        for (int i = 0; i < sz; i++, hs1 ^= nw & -nw, nw ^= nw & -nw) {
            qu[1].push_back(qu[2].back());
            qu[2].pop_back();
            tst();
        }
        for (int i = 0; i < sz; i++) qu[1].pop_back();

        nw = hs;
        for (vector<P>::iterator ite = qu[0].begin(); ite != qu[0].end(); ite++)
            qu[1].push_back(*ite);

        hs1 ^= nw & -nw, nw ^= nw & -nw;
        for (int i = 0; i < sz; i++, hs1 ^= nw & -nw, nw ^= nw & -nw) {
            qu[2].push_back(qu[1].back());
            qu[1].pop_back();
            tst();
        }
        for (int i = 0; i < sz; i++) qu[2].pop_back();
    }
    qu[0].clear();
    qu[1].clear();
    qu[2].clear();
}

int main() {
    scanf("%d", &n);
    MA = (1ll << n) - 1;
    for (int i = 0; i < n; i++) {
        scanf("%d%d", &in1, &in2);
        nd.push_back(P(in1, in2));
    }
    sort(nd.begin(), nd.end());

    for (vector<P>::iterator it = nd.begin(); it != nd.end(); it++)
        for (vector<P>::iterator ite = it + 1; ite != nd.end(); ite++)
            dfs(*it, *ite);

    printf("%llu", res);
    return 0;
}

代码说明

• dfs函数：枚举划分直线并进行点集分类
• wk2函数：验证几何约束并统计合法方案
• tst函数：检查距离约束条件
• 使用位运算哈希避免重复计算
• 动态规划统计满足条件的分配方案

复杂度分析

• 时间复杂度：$O(n^3)$，主要来自点对枚举和DP计算
• 空间复杂度：$O(n^2)$，用于存储DP状态