卡菈一如繼往的與艾爾文在到處闖蕩。今天他們來到了一個地窖,裡面有一個魔法陣,而魔法陣的四周有許多機關,卡菈希望能發射一個魔法彈去觸碰那些機關而不觸及魔法陣,但是他不太確定要以什麼角度發射才不會不小心撞到魔法陣,因此他需要你幫他計算可能的交點,或回報並不會相交。
具體來說我們可以把魔法陣視為一個二維平面上的圓,而卡菈射出的魔法彈則會構成一條直線,因此我們想知道給定一個圓及一條直線,他們的交點為何,或是回報不存在。
以下為提供的解法,請構造出一筆滿足題目條件的測資讓該程式碼的輸出不是一些實數或 none
:
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
namespace {
using llf = long double;
using PTF = complex<llf>;
const llf eps = 1e-8;
llf dot(PTF a, PTF b) { return real(conj(a) * b); }
PTF project(PTF p, PTF q) { return dot(p, q) * q / dot(q, q); }
llf Sqrt(llf x) {
if (llf v = sqrt(x); isnan(v))
return 0;
else
return v;
}
struct L {
PTF st, ed, dir;
L(PTF s, PTF e) : st(s), ed(e), dir(e - s) {}
};
vector<PTF> interCircle(const L &l, const PTF &c, llf r) {
PTF ft = l.st + project(c - l.st, l.dir);
if (llf dis = abs(c - ft); dis > r + eps)
return {};
else if (llf d = Sqrt(r * r - dis * dis); d == 0)
return {ft};
else {
PTF vec = l.dir * d / abs(l.dir);
return {ft + vec, ft - vec};
}
};
} // namespace
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int x1, y1, x2, y2;
int x0, y0, r;
cin >> x1 >> y1 >> x2 >> y2;
cin >> x0 >> y0 >> r;
L l(PTF(x1, y1), PTF(x2, y2));
PTF c(x0, y0);
auto p = interCircle(l, c, r);
if (p.empty()) {
cout << "none\n";
} else {
for (auto pi : p)
cout << fixed << setprecision(10) << pi.real() << " " << pi.imag()
<< '\n';
}
return 0;
}
第一行有四個整數 $x_1$, $y_1$, $x_2$, $y_2$,代表卡菈射出的魔法彈會穿過點 $(x_1, y_1)$ 與 $(x_2, y_2)$。
第二行有三個整數 $x_0$, $y_0$, $r$,代表魔法陣的中心位在 $(x_0, y_0)$,且半徑為 $r$。
若兩者沒交點,則請輸出一行 none
。
否則,請在第 $i$ 行輸出第 $i$ 個交點 $(x_i, y_i)$(以任意順序輸出交點皆可)
只要與答案的絕對誤差或相對誤差少於 $10^ {-6}$ 皆會被接受。
以下程式碼能產生本題合法但一定不會讓你得到 AC 的測試資料:
#include<stdio.h>
int main(){
printf("%d %d %d %d\n",0,0,1,1);
puts("10 10 1");
}
IOICamp 2023 Day1 pA
No. | Testdata Range | Score |
---|---|---|
1 | 0 | 100 |