ZeroJudge 解題筆記：b603. 拋物線方程式

作者：王一哲
日期：2025年7月30日


ZeroJudge 題目連結：b603. 拋物線方程式

解題想法

這題考數學。假設開口向上或向下的抛物線頂點為 $(h, k) = (x_1, y_1)$，其方程式為 $$ y = A(x-h)^2 + k = A(x-x_1)^2 + y_1 $$ 線上另一個點為 $(x_2, y_2)$，將這個點代入上式可得 $$ y_2 = A(x_2 - x_1)^2 + y_1 ~\Rightarrow~ A = \frac{y_2 - y_1}{(x_2 - x_1)^2} $$ 另外二次曲線的通式為 $$ y = Ax^2 + Bx + C $$ 將上式與第1式比較係數，由 $x$ 項可得 $$ B = -2Ax_1 = -2 \times \frac{y_2 - y_1}{(x_2 - x_1)^2} \times x_1 $$ 由常數項可得 $$ C = Ax_1^2 + y_1 = \frac{y_2 - y_1}{(x_2 - x_1)^2} \times x_1^2 + y_1 $$ 為了將係數化為整數，將每一項同乘以 $x_2 - x_1$，再換成此題要求的型式 $ay = bx^2 + cx + d$，4個係數分別為 $$ \begin{align*} a &= x_2 - x_1 \\ b &= (x_2 - x_1) A = \frac{y_2 - y_1}{x_2 - x_1} \\ c &= (x_2 - x_1) B = -\frac{2x_1 (y_2 - y_1)}{x_2 - x_1} \\ d &= (x_2 - x_1) C = \frac{x_1^2 (y_2 - y_1)}{x_2 - x_1} + y_1 (x_2 - x_1) \end{align*} $$ 因為 $a$ 必須是正值，最後要再檢查一下係數的正負號。由以上的公式得到的係數可能需要約分。

Python 程式碼

第9行的 math.gcd，我使用的 Python 版本為 3.10.12，可以一次輸入多個參數求最大公因數，但是 ZeroJudge 網站的 Python 版本為 3.6.9，每次只能輸入2個參數。使用時間約為 21 ms，記憶體約為 3.4 MB，通過測試。

from math import gcd

def solve(x1, y1, x2, y2):
    a = x2-x1
    b = (y2-y1)//(x2-x1)
    c = -2*x1*(y2-y1)//(x2-x1)
    d = x1*x1*(y2-y1)//(x2-x1) + y1*(x2-x1)
    if a < 0:
        a, b, c, d = -a, -b, -c, -d
    g = gcd(gcd(gcd(a, b), c), d)
    if g != 1:
        a, b, c, d = a//g, b//g, c//g, d//g
    return a, b, c, d

while True:
    try:
        x1, y1, x2, y2 = map(int, input().split())
        a, b, c, d = solve(x1, y1, x2, y2)
        print(f"{a:d}y = {b:d}x^2 + {c:d}x + {d:d}")
    except EOFError: break

C++ 程式碼

使用時間約為 2 ms，記憶體約為 84 kB，通過測試。

#include <cstdio>
#include <algorithm>
using namespace std;

int main() {
    int x1, y1, x2, y2, a, b, c, d, g;
    while(scanf("%d %d %d %d", &x1, &y1, &x2, &y2) != EOF) {
        a = x2-x1;
        b = (y2-y1)/(x2-x1);
        c = -2*x1*(y2-y1)/(x2-x1);
        d = x1*x1*(y2-y1)/(x2-x1) + y1*(x2-x1);
        if (a < 0) {
            a = -a, b = -b, c = -c, d = -d;
        }
        g = __gcd(__gcd(__gcd(a, b), c), d);
        if (g != 1) {
            a /= g, b /= g, c /= g, d /= g;
        }
        printf("%dy = %dx^2 + %dx + %d\n", a, b, c, d);
    }
    return 0;
}