0

座標（P x、P y）と（Q x、Q y ）を持つ2つの点PとQは、次の特性を満たします。

  1. 座標Px 、 P y、Q x、およびQyは整数です。
  2. P x = −Qx。
  3. 線PQは、中心（0、0）と半径rの円に接しています。
  4. ある整数制限aに対して0 < Px≤a。

そのような点PとQのすべてのペアを見つけるにはどうすればよいですか？

たとえば、次の画像では、半径r = 2、極限a = 6の円があります。点のペアP=（6、2）とQ =（-6、-7）は、次の理由で解決策になります。

  1. PとQの座標は整数です。
  2. P x = −Qx。
  3. 線PQは円に接しています。
  4. 0< Px≤6。

しかし、これは1つのペアにすぎません。私はそのようなペアをすべて見つける必要があります。解決策の数には限りがあります。

それで、点の座標が円に接していて整数であるかどうかをチェックして、それらすべてをリストする方法はありますか？傾きの方程式と、円の中心から一次方程式までの最短経路を見てきましたが、最初のケースでは、座標を知る必要があります（これは、1桁ごとにブルートフォースすることで実行できますが、パターン、私の内臓は私が適用すべきある種の方程式があるべきだと私に言うので）、そして2番目のケースでは私は勾配方程式を知らなければなりません。

これは私が思いついたアルゴリズムですが、それが正しいか十分ではないと思います。

  1. すべての1≤Px≤aおよび-<em>a≤Qx≤-1について、勾配方程式y = mx + bを見つけます。
  2. すべてのy = mx + bについて、それが円に接しているかどうかを確認します（これを行う方法???）
  3. trueの場合、ペアを返します
4

1 に答える 1

0

ラインPQには次の式があります。

(x-Px)/(Qx-Px)=(y-Py)/(Qy-Py) or

(x-Px)*(Qy-Py)-(y-Py)*(Qx-Px)=0 or

x*(Qy-Py)+y*(Px-Qx)-Px*Qy+Px*Py+Py*Qx-Py*Px = 

x*(Qy-Py)+y*2*Px-Px*(Qy+Py)=0

ゼロ点からこの線までの距離（円の半径）は

r=Px*(Qy+Py)/Sqrt((2*Px)^2+(Qy-Py)^2)

半径と分母は整数であるため、分母も整数である必要があることに注意してください。2*Pxおよび|Qy-Py|の場合に可能です。はいくつかのピタゴラストリプルのメンバーです（たとえば、-12 ^ 2 + 9 ^ 2 = 15 ^ 2）。したがって、上記のリンクから「トリプルの生成」メソッドを使用して、検索を大幅に減らし、可能なすべてのポイントペアを見つけることができます。 （半径チェック付き）

  Px = k * m * n   (for m>=n, radius < k*m*n <= a)
  |Qy-Py| = k * (m^2 - n^2)

a = 6の場合、nの最大値は2であり、例は（3、2、1）の（k、m、n）セットに対応します。

于 2013-01-18T11:50:29.543 に答える