b603 - 拋物線方程式

🔗 前往 ZeroJudge 原題

題目描述

題目給定拋物線的頂點座標 (x1, y1) 和拋物線上一點的座標 (x2, y2)，要求輸出拋物線方程式 ay = bx^2 + cx + d。輸出時，a 為正整數，b, c, d 為整數，且所有係數都必須顯示，即使係數為 1 或 -1。等號和加號前後需要有空白。

解題思路

拋物線方程式的一般形式為 y = a(x - h)^2 + k，其中 (h, k) 是頂點座標。已知頂點 (x1, y1)，則方程式可以寫成 y = a(x - x1)^2 + y1。 由於拋物線經過點 (x2, y2)，我們可以將該點的座標代入方程式，解出 a 的值： y2 = a(x2 - x1)^2 + y1 a = (y2 - y1) / (x2 - x1)^2

求出 a 後，將其展開並整理成 ay = bx^2 + cx + d 的形式。 展開後：y = a(x^2 - 2x1x + x1^2) + y1 = ax^2 - 2ax1x + ax1^2 + y1 整理成 ay = bx^2 + cx + d 的形式： ay = a^2x^2 - 2a^2x1x + a^2x1^2 + ay1 因此，b = a^2, c = -2a^2x1, d = a^2x1^2 + ay1。

最後，為了簡化方程式，需要計算 a, b, c, d 的最大公約數 (GCD)，並將所有係數除以 GCD。

複雜度分析

• 時間複雜度: O(1)
• 空間複雜度: O(1)

程式碼

#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <stdio.h>
#include <algorithm>
using namespace std;
int main(){
	int x1,y1,x2,y2;
	while(scanf("%d%d%d%d",&x1,&y1,&x2,&y2)>0){
		int b(y2-y1),x21(x2-x1),a(x21*x21),c(-(x1<<1)*b),d(b*x1*x1 + y1*a),g(__gcd(a, b));
		g = __gcd(g, c), g = __gcd(g, d);
		printf("%dy = %dx^2 + %dx + %d\n",a/g,b/g,c/g,d/g);
	}
}