计算几何？

prob

题意简述

给你 nn 个点 pi=(xi,yi)p_i=(x_i,y_i) ，问你有多少条过原点的直线满足：所有点在该直线上的投影呈轴对称。若有无穷个直线输出 −1-1 。

题解

考虑我们有一条直线 y=kxy=kx ，为了避免误差我们用向量表示 (a,b),k=ba(a,b),k=\dfrac{b}{a} 。

考虑 nn 个点在该直线上的投影，可以用 点积，考虑其几何意义：从原点到某点 pip_i 的向量在直线上的投影 乘上 向量 (a,b)(a,b) 的长度。这可以表示每个点在直线上投影的相对位置。

我们已经把二维转化成一维了，接着要满足 nn 个数在数轴上对称。若对称必然存在一个中心点为所有点的平均值，即 o=1n∑i=1naxi+byio = \frac{1}{n}\sum_{i=1}^n ax_i+by_i ，易得其在二维平面上的点为 O(∑i=1nxin,∑i=1nyin)O\left(\dfrac{\sum_{i=1}^n x_i}{n},\dfrac{\sum_{i=1}^{n}y_i}{n}\right) 。

若存在某对点 pi,pjp_i,p_j 关于 OO 对称，那么无论直线怎么取，它们投影都对称，可以删掉。若删到没有点，或者剩下的点在 OO 上则无穷解。

现在还剩 mm 个点，一条合法的直线必然有 ⌊m2⌋\left\lfloor\frac{m}{2}\right\rfloor 对对称点。我们枚举一对点 pi,pjp_i,p_j 使其对称：

2(axO+byO)=axi+byi+axj+byj2(ax_O+by_O)=ax_i+by_i+ax_j+by_j

可解出 k=bak=\dfrac{b}{a} 。

我们搞出了 O(m2)O(m^2) 条直线，由于一条合法的直线必然有 ⌊m2⌋\left\lfloor\frac{m}{2}\right\rfloor 对对称点。可能合法的直线必须被枚举到 ⌊m2⌋\left\lfloor\frac{m}{2}\right\rfloor 次，故我们只需要判断 m2m/2=O(m)\dfrac{m^2}{m/2}=O(m) 条直线，每次 O(mlog⁡m)O(m\log m) 判断即可。

总复杂度 O(n2log⁡n)O(n^2\log n) 。

注意用 (a,b)(a,b) 表示 kk 时，要化到最简整数比，还有正负号（ (0,1)(0,1) 和 (0,−1)(0,-1) 是相同的）。

CODE

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include <bits/stdc++.h>
template <typename Tp>
inline void read(Tp& x) {
    x = 0; bool fg = 0; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') fg ^= 1; ch = getchar();}
    while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (Tp)(ch ^ 48), ch = getchar();
    if (fg) x = -x;
}
template <typename Tp, typename... Args>
void read(Tp& t, Args& ...args) { read(t); read(args...); }
using namespace std;
typedef long long ll;
const int N = 500010;
const int mod = 998244353;
int head[N], pnt[N << 1], nxt[N << 1], E;
int n, deg[N], cnt, rt1, rt2, len;
int dep1[N], dep2[N];
ll f[N];
ll fpow(ll a, ll b = mod - 2, ll p = mod) {
    ll r = 1;
    for ( ; b; b >>= 1, a = a * a % mod) if (b & 1) r = (r * a) % mod;
    return r;
}

void adde(int u, int v) {
    ++E; pnt[E] = v; nxt[E] = head[u]; head[u] = E;
}

void dfs(int u, int f, int d, int *ds) {
    ds[u] = d;
    for (int i = head[u]; i; i = nxt[i]) {
        int v = pnt[i];
        if (v == f) continue;
        dfs(v, u, d + 1, ds);
    }
}
int Count, tot;
void DFS(int u, int f, int d) {
    if (d == len / 2) ++Count;
    for (int i = head[u]; i; i = nxt[i]) {
        int v = pnt[i];
        if (v == f) continue;
        DFS(v, u, d + 1);
    }
}
int main() {
    read(n);
    for (int i = 1; i < n; ++i) {
        int u, v; read(u, v);
        adde(u, v); adde(v, u);
        ++deg[u], ++deg[v];
    }
    for (int i = 1; i <= n; ++i) if (deg[i] == 1) ++cnt;
    dfs(1, 0, 0, dep1);
    for (int i = 1; i <= n; ++i) if (dep1[i] > dep1[rt1]) rt1 = i;
    dfs(rt1, 0, 0, dep1);
    for (int i = 1; i <= n; ++i) if (dep1[i] > dep1[rt2]) rt2 = i;
    dfs(rt2, 0, 0, dep2);
    len = dep1[rt2];
    vector<int> A;
    if (len % 2 == 0) {
        for (int i = 1; i <= n; ++i) {
            if (dep1[i] == dep2[i] && dep1[i] == len / 2) rt1 = i;
        }
        for (int i = head[rt1]; i; i = nxt[i]) {
            Count = 0;
            DFS(pnt[i], rt1, 1);
            if (Count != 0) tot += Count, A.push_back(Count);
        }
    } else {
        for (int i = 1; i <= E; i += 2) {
            int u = pnt[i], v = pnt[i + 1];
            if (min(dep1[u], dep2[u]) == len / 2 && min(dep1[v], dep2[v]) == len / 2)
                rt1 = u, rt2 = v;
        }
        Count = 0;
        DFS(rt1, rt2, 0);
        if (Count) A.push_back(Count), tot += Count;
        Count = 0;
        DFS(rt2, rt1, 0);
        if (Count) A.push_back(Count), tot += Count;
    }
    for (int i = 1; i <= cnt; ++i) f[i] = (f[i - 1] + cnt * fpow(i)) % mod;
    ll ans = 0;
    for (int i = 0; i < (int)A.size(); ++i) {
        ans = (ans + f[tot - A[i]]) % mod;
    }
    ans = (ans - f[tot] * (A.size() - 1) % mod + mod) % mod;
    cout << ans << endl;
    return 0;
}