c905 - 求直線與圓的交點
題目描述
題目要求計算給定圓和直線的交點座標。需要考慮直線與圓相交於兩個點、相切於一點以及沒有交點的三種情況。輸出格式要求保留小數點後五位，並按照 x 座標從小到大輸出交點。
解題思路
解題思路是首先判斷直線與圓是否相交。判斷方法是計算圓心到直线的距離，如果距離小於或等於圓的半徑，則直線與圓相交。如果相交，則計算交點的座標。計算交點的座標可以使用直線的參數方程和圓的方程聯立求解。具體步驟如下：
- 計算圓心到直线的距離。
- 如果距離大於圓的半徑，則直線與圓沒有交點，輸出 "No Intersect"。
- 如果距離等於圓的半徑，則直線與圓相切，計算切點座標並輸出兩個相同的座標。
- 如果距離小於圓的半徑，則直線與圓相交於兩點，計算兩個交點的座標，按照 x 座標從小到大輸出。
程式碼中 IfIntersect 函數用於判斷直線與圓是否相交，FindIntersect 函數用於計算交點座標，IfOnLine 函數用於判斷點是否在直線上。
複雜度分析
- 時間複雜度: O(T)，其中 T 是測試案例的數量。對於每個測試案例，計算距離和交點座標的時間複雜度都是 O(1)。
- 空間複雜度: O(1)。程式碼使用的額外空間是常數級別的。
程式碼
#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;
#define ERROR 1e-7
bool IfIntersect(int x1, int y1, int x2, int y2, int xc, int yc, int radius) {
int buf1 = x1 - x2, buf2 = y1 - y2, buf3 = buf1 * y1 - buf2 * x1;
double dis = abs(buf2 * xc - buf1 * yc + buf3) / sqrt(buf1 * buf1 + buf2 * buf2);
if (dis < radius || abs(dis - radius) < ERROR)return 1;
return 0;
}
bool IfOnLine(int x1, int y1, int x2, int y2, double x, double y) {
int buf1 = x1 - x2, buf2 = y1 - y2, buf3 = buf1 * y1 - buf2 * x1;
double dis = buf2 * x - buf1 * y + buf3;
if (abs(dis) < ERROR)return 1;
return 0;
}
void FindIntersect(int x1, int y1, int x2, int y2, int xc, int yc, int radius) {
int buf1 = x1 - x2, buf2 = y1 - y2, buf3 = buf1 * y1 - buf2 * x1;
double buf4 = sqrt(buf1 * buf1 + buf2 * buf2), dis = abs(buf2 * xc - buf1 * yc + buf3) / buf4;
double buf5 = sqrt(radius * radius - dis * dis), newX1 = xc + dis / buf4 * buf2, newY1 = yc - dis / buf4 * buf1, newX2, newY2;
if (!IfOnLine(x1, y1, x2, y2, newX1, newY1))
newX1 = xc - dis / buf4 * buf2, newY1 = yc + dis / buf4 * buf1;
newX2 = newX1 + buf5 / buf4 * buf1, newY2 = newY1 + buf5 / buf4 * buf2;
newX1 -= buf5 / buf4 * buf1, newY1 -= buf5 / buf4 * buf2;
if (newX2 + ERROR < newX1)
swap(newX1, newX2), swap(newY1, newY2);
cout << fixed << setprecision(5) << newX1 << ' ' << newY1 << ' ' << newX2 << ' ' << newY2 << '\n';
}
int main() {
cin.sync_with_stdio(0), cin.tie(0), cout.tie(0);
int x1, y1, x2, y2, xc, yc, radius, times;
for(cin >> times;times--;) {
cin >> xc >> yc >> radius >> x1 >> y1 >> x2 >> y2;
if (!IfIntersect(x1, y1, x2, y2, xc, yc, radius))
cout << "No Intersect\n";
else
FindIntersect(x1, y1, x2, y2, xc, yc, radius);
}
}