题解：CF593C Beautiful Function

感谢大神 @Swirl 指点，大家都去关注喵。

不错的题。

---

看到这个首先想到拉插（拉格朗日插值法，大概就是可以给任意数列找通项公式），但我们没有除法。

我们尝试简化问题，将 $n$ 个圆看作 $n$ 个圆的圆心，那么就可以把 $f(x)$ 和 $g(x)$ 独立来看。

我们还是往拉插方面想，其本质大概是一堆函数相加，每个都是下面这种形式。

$$f(x) = \begin{cases} b, & x = a \\ 0, & x \neq a \end{cases}$$

那把这个函数构造出来就没问题了。

这貌似是整题最难的部分，经过 Gemini 老师的指点，令 $k = \frac{b}{2}$，我们得到了下面这个简短的式子。

$$f(x) = k \times ( \ | \ |x - a| - 1 \ | - |x - a| + 1 \ )$$

问题来了，根据题意，$k$ 只能为整数，这显然会在 $b$ 为奇数时坠机。

但我们注意到 $2 \le r$，所以我们直接除以 $2$ 向下取整，差出来的 $1$ 是能接受的，那就没问题了。

因为加法外面要打括号，建议写成往两边递归，不然实在有点难写了。

按习惯来说，spj 题我一般会挂上个 spj 用来自查，但这个东西实在难实现了，就咕咕了。

---

/******************************
 - @GavinCQTD
 - "C. Beautiful Function"
 - # https://codeforces.com/problemset/problem/593/C
 - 2000 ms
******************************/

#include <iostream>
#include <cassert>
#include <string>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;

int n,x[55],y[55];

string solve(int a[],int l,int r){
    if(l==r){
        // (k*(abs((abs((t−a))−1))−(abs((t−a))−1)))
        return "("+to_string(a[l]/2)+"*(abs((abs((t-"+to_string(l)
            +"))-1))-(abs((t-"+to_string(l)+"))-1)))";
    }
    int mid=(l+r)/2;
    return "("+solve(a,l,mid)+"+"+solve(a,mid+1,r)+")";
}

int main(){
    cin >> n;
    for(int i=1;i<=n;i++){
        int r;
        cin >> x[i] >> y[i] >> r;
    }

    cout << solve(x,1,n) << "\n" << solve(y,1,n) << "\n";

    return 0;
}

---

upd:

还是丢个 Python 写的 spj 在这，要用的自取，直接运行就好。

import sys


def readData():
    print("Input data:")
    n = int(sys.stdin.readline().strip())

    circles = []
    for _ in range(n):
        parts = list(map(int, sys.stdin.readline().split()))
        if len(parts) == 3:
            xi, yi, ri = parts
            circles.append((xi, yi, ri))

    print("\nInput f(t):")
    f = sys.stdin.readline().strip()

    if f.count("*") > 50:
        print("f(t) contains too many multiplications.")
        sys.exit(1)

    print("\nInput g(t):")
    g = sys.stdin.readline().strip()

    if g.count("*") > 50:
        print("g(t) contains too many multiplications.")
        sys.exit(1)

    return circles, f, g


def generatePoints(f, g):
    points = []

    for t in range(51):
        x = eval(f, {"t": t})
        y = eval(g, {"t": t})
        points.append((x, y))

    return points


def main():
    circles, f, g = readData()

    points = generatePoints(f, g)

    print("\nGenerated points:")
    for t, (x, y) in enumerate(points):
        print(f"t={t}: ({x}, {y})")

    for t, (x, y) in enumerate(points):
        if not (-10**9 <= x <= 10**9 and -10**9 <= y <= 10**9):
            print(f"Point at t={t} ({x}, {y}) is out of bounds.")
            sys.exit(1)

    valid_circles = [False] * len(circles)

    print("\nCircles containing points:")
    for i, (xi, yi, ri) in enumerate(circles):
        for t, (x, y) in enumerate(points):
            if (x - xi) ** 2 + (y - yi) ** 2 <= ri**2:
                valid_circles[i] = True
                print(
                    f"Circle {i} contains point at t={t} ({points[t][0]}, {points[t][1]}), dis: {((x - xi) ** 2 + (y - yi) ** 2) ** 0.5:.2f}"
                )

    print("\nResult:")
    for i, valid in enumerate(valid_circles):
        if not valid:
            print(f"Circle {i} does not contain any points.")

    if all(valid_circles):
        print("All circles contain at least one point.")


if __name__ == "__main__":
    main()