TopCoder

Caido
主唱太拼命了

User's AC Ratio

100.0% (4/4)

Submission's AC Ratio

100.0% (6/6)

Tags

Description

卡菈一如繼往的與艾爾文在到處闖蕩。今天他們來到了一個地窖,裡面有一個魔法陣,而魔法陣的四周有許多機關,卡菈希望能發射一個魔法彈去觸碰那些機關而不觸及魔法陣,但是他不太確定要以什麼角度發射才不會不小心撞到魔法陣,因此他需要你幫他計算可能的交點,或回報並不會相交。

具體來說我們可以把魔法陣視為一個二維平面上的圓,而卡菈射出的魔法彈則會構成一條直線,因此我們想知道給定一個圓及一條直線,他們的交點為何,或是回報不存在。

以下為提供的解法,請構造出一筆滿足題目條件的測資讓該程式碼的輸出不是一些實數或 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;
}

Input Format

第一行有四個整數 $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$。

  • $(x_1, y_1) \neq (x_2, y_2)$
  • $|x_1|$, $|y_1|$, $|x_2|$, $|y_2|$, $|x_0|$, $|y_0|$, $r$ $\leq 10^ 9$

Output Format

若兩者沒交點,則請輸出一行 none

否則,請在第 $i$ 行輸出第 $i$ 個交點 $(x_i, y_i)$(以任意順序輸出交點皆可)

只要與答案的絕對誤差或相對誤差少於 $10^ {-6}$ 皆會被接受。

Sample Input 1

0 0 1 1
10 -10 1

Sample Output 1

none

Hints

以下程式碼能產生本題合法但一定不會讓你得到 AC 的測試資料:

#include<stdio.h>
int main(){
  printf("%d %d %d %d\n",0,0,1,1);
  puts("10 10 1");
}

Problem Source

IOICamp 2023 Day1 pA

Subtasks

No. Testdata Range Score
1 0 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 65536 1