d141 - Linearity

🔗 前往 ZeroJudge 原題

題目描述

題目要求判斷三個給定的二維座標點是否共線。輸入包含多個測試案例，每個案例包含三個點的座標，以逗號分隔 x 和 y 座標，以空格分隔各個點。對於每個案例，輸出 "collinear" 如果三點共線，否則輸出 "not collinear"。

解題思路

判斷三點是否共線，可以使用斜率公式。如果三點共線，則任意兩點之間的斜率都應該相等。然而，為了避免除以零的錯誤，可以改用以下等價條件：對於點 (x1, y1), (x2, y2), (x3, y3)，如果它們共線，則 (y2 - y1) * (x3 - x2) == (y3 - y2) * (x2 - x1)。程式碼中直接使用了這個等價條件的變形：(a-c)(b-f) == (b-d)(a-e)。

複雜度分析

• 時間複雜度: O(T)，其中 T 是測試案例的數量。對於每個案例，執行常數次數的算術運算。
• 空間複雜度: O(1)，程式只使用了常數個變數。

程式碼

#include <iostream>
using namespace std;
int main(){
	long long int t,a,b,c,d,e,f;
	char p;
	cin >> t;
	while(t--){
		cin >> a >> p >>  b >> c >> p >> d >> e >> p >> f;
		int ac=a-c,bd=b-d,ae=a-e,bf=b-f;
		if(ac*bf==bd*ae)
			cout << "collinear\n";
		else
			cout << "not collinear\n";
	}
}