A. ICPC Shenyang in NEU, the Tenth Consecutive Year

题目大意：

你要猜一个 $1923 \sim 2023$ 之间的整数，询问次数不超过 $100$ 次。

解题思路：

直接枚举会超过 $100$ 次限制，但是容易发现只要询问完 $1923 \sim 2022$ 之间的数即可，如果都返回 $0$ 直接输出 $2023$。

#include <bits/stdc++.h>

constexpr int N = 1e5 + 6;

void solve() {
    for (int i = 1923; i <= 2022; ++i) {
        std::cout << "? " << i << std::endl;
        int x;
        std::cin >> x;
        if (x == 1) {
            std::cout << "! " << i << std::endl;
            return;
        }
    }
    std::cout << "! " << 2023 << std::endl;
}

int main() {
  // std::ios::sync_with_stdio(0);
  // std::cin.tie(0), std::cout.tie(0);

  int t;
  std::cin >> t;
  // t = 1;

  while (t--) {
    solve();
  }

  return 0;
}

B. Computational Intelligence$^2$

题目大意：

给定两条线段，你要在两条线段上随机选一个点，求两点平面欧几里得距离平方的期望值。

解题思路：

我们先考虑用 $P$ 和 $Q$ 表示线段一和线段二的点：

$$P(x_1 + t(x_2 - x_1), y_1 + t(y_2 - y_1)) \\ Q(x_3 + s(x_4 - x_3), y_3 + s(y_4 - y_3))$$

其中 $0 \le s, t \le 1$。

则 $P$ 和 $Q$ 的平面欧几里得距离的平方为：

$$\begin{aligned} D(P, Q) &= [x_1 + t(x_2 - x_1) - x_3 - s(x_4 - x_3)] ^ 2 + [y_1 + t(y_2 - y_1) - y_3 - s(y_4 - y_3)] ^ 2 \\ &= [(x_1 - x_3) + t(x_2 - x_1) - s(x_4 - x_3)] ^ 2 + [(y_1 - y_3) + t(y_2 - y_1) - s(y_4-y_3)] ^ 2 \end{aligned}$$

令：

$$\left\{\begin{aligned} A &= x_1 - x_3 \\ B &= x_2 - x_1 \\ C &= -(x_4 - x_3) \\ D &= y_1 - y_3 \\ E &= y_2 - y_1 \\ F &= -(y_4 - y_3) \end{aligned}\right.$$

带入原式，得：

$$\begin{aligned} D(P, Q) &= (A + tB + sC)^2 + (D + tE + sF) ^ 2 \\ &= A^2 + t^2B^2 + s^2C^2 + 2ABt + 2ACs + 2BCts + D^2+t^2E^2+s^2F^2 + 2DEt+2DFs+2EFts \\ &= (A^2+D^2)+(B^2+E^2)t^2+(C^2+F^2)s^2+(2BC + 2EF)ts + (2AB + 2DE)t + (2AC + 2DF)s \\ &= (B^2+E^2)t^2+(2AB + 2DE)t+(C^2+F^2)s^2+(2AC + 2DF)s+(2BC + 2EF)ts + (A^2+D^2) \end{aligned}$$

再令：

$$\left\{\begin{aligned} a &= B^2+E^2 \\ b &= 2AB + 2DE\\ c &= C^2 + F^2 \\ d &= 2AC + 2DF \\ e &= 2BC + 2EF \\ f &= A^2+D^2 \end{aligned}\right.$$

带入原式，得：

$$D(P, Q) = at^2+bt+cs^2+ds+ets+f$$

那么，根据期望的线性性质，答案为：

$$\begin{aligned} E(D(P, Q)) &= E(at^2+bt+cs^2+ds+ets+f) \\ &= aE(t^2) + bE(t) + cE(s^2) + dE(s) + eE(t)E(s) + f \end{aligned}$$

接下来我们考虑计算各项期望值：

• $E(s)$ 和 $E(t)$：由于 $0 \le s, t \le 1$，所以这两个为 $\displaystyle\frac{1}{2}$。

• $E(s^2)$ 和 $E(t^2)$：非常简单，小学微积分题，答案为：

$$\begin{aligned} \frac{\displaystyle\int_{0}^1 x^2 \mathrm dx}{1} &= \int_{0}^1 x^2 \mathrm dx &= \frac{1}{3} \end{aligned}$$

那么最终答案为：

$$\frac{a}{3} + \frac{b}{2} + \frac{c}{3} + \frac{d}{2} + \frac{e}{4} + f$$

时间复杂度 $O(1)$。

代码如下：

#include <bits/stdc++.h>

constexpr int N = 1e5 + 6;

void solve() {
    double x1, y1, x2, y2, x3, y3, x4, y4;
    std::cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3 >> x4 >> y4;
    double A = x1 - x3;
    double B = x2 - x1;
    double C = -(x4 - x3);
    double D = y1 - y3;
    double E = y2 - y1;
    double F = -(y4 - y3);
    double a = B * B + E * E;
    double b = 2 * (A * B + D * E);
    double c = C * C + F * F;
    double d = 2 * (A * C + D * F);
    double e = 2 * (B * C + E * F);
    double f = A * A + D * D;
    double ans = a / 3.0 + b / 2.0 + c / 3.0 + d / 2.0 + e / 4.0 + f;
    std::cout << std::fixed << std::setprecision(10) << ans << "\n"; 
}

int main() {
  std::ios::sync_with_stdio(0);
  std::cin.tie(0), std::cout.tie(0);

  int t;
  std::cin >> t;
  // t = 1;

  while (t--) {
    solve();
  }

  return 0;
}