E085. Пересечение окружности и прямой

e-maxx algorithm original: C/C++ #algorithm #emaxx #geometry #math

Le texte du problème est traduit du russe pour la langue sélectionnée. Le code reste inchangé.

Static

Источник: e-maxx.ru/algo, страница PDF 246.

Дана окружность (координатами своего центра и радиусом) и прямая (своим уравнением). it is required find точки их пересечения (одна, две, либо ни одной).

Solution

Вместо формального решения системы двух уравнений подойдём к задаче с геометрической стороны (причём, за счёт этого мы получим более точное Solution с точки зрения численной устойчивости). Предположим, не теряя общности, что центр окружности находится в начале координат (если это не так, то перенесём его туда, исправив соответствующе константу C в уравнении прямой). Т.е. имеем окружность с центром в (0,0) радиуса r и прямую с уравнением Ax + By + C = 0. Сначала найдём ближайшую к центру точку прямой - точку с некоторыми координатами (x0,y0). Во- первых, эта точка должна находиться на таком расстоянии от начала координат:

|C|

----------

sqrt(A2+B2)

Во-вторых, поскольку вектор (A,B) перпендикулярен прямой, то координаты этой точки должны быть пропорциональны координатам этого вектора. given, что расстояние от начала координат до искомой точки нам известно, нам нужно просто нормировать вектор (A,B) к этой длине, и мы получаем:

A C

x0 = - -----

A2+B2

B C

y0 = - -----

A2+B2

(здесь неочевидны только знаки 'минус', но эти формулы легко проверить подстановкой в уравнение прямой -

должен получиться ноль)

Зная ближайшую к центру окружности точку, мы уже можем определить, сколько точек будет содержать ответ, и даже дать ответ, если этих точек 0 или 1. Действительно, если расстояние от (x0, y0) до начала координат (а его мы уже выразили формулой - см. выше) больше радиуса, то ответ - ноль точек. Если это расстояние равно радиусу, то ответом будет одна точка - (x0,y0). А вот в оставшемся случае точек будет две, и их координаты нам предстоит find. Итак, мы знаем, что точка (x0, y0) лежит внутри круга. Искомые точки (ax,ay) и (bx,by), помимо того что должны принадлежать прямой, должны лежать на одном и том же расстоянии d от точки (x0, y0), причём это расстояние легко find:

C2

d = sqrt ( r2 - ----- )

A2+B2

Заметим, что вектор (-B,A) коллинеарен прямой, а потому искомые точки (ax,ay) и (bx,by) можно получить, прибавив к точке (x0,y0) вектор (-B,A), нормированный к длине d (мы получим одну искомую точку), и вычтя этот же вектор (получим вторую искомую точку). Окончательное Solution такое:

d2

mult = sqrt ( ----- )

A2+B2

ax = x0 + B mult

ay = y0 - A mult

bx = x0 - B mult

by = y0 + A mult

Если бы мы решали эту задачу чисто алгебраически, то скорее всего получили бы Solution в другом виде, которое даёт бОльшую погрешность. Поэтому "геометрический" метод, описанный здесь, помимо наглядности, ещё и более точен.

Implémentation

Как и было указано в начале описания, предполагается, что окружность расположена в начале координат. Поэтому Entréeные параметры - это радиус окружности и коэффициенты A,B,C уравнения прямой.

double r, a, b, c; // Entréeные данные

double x0 = -ac/(aa+bb), y0 = -bc/(aa+bb);

if (c*c > r*r*(a*a+b*b)+EPS)

puts ("no points");

else if (abs (cc - rr*(aa+bb)) < EPS) {

puts ("1 point");

cout << x0 << ' ' << y0 << '\n';

}

else {

double d = rr - cc/(aa+bb);

double mult = sqrt (d / (aa+bb));

double ax,ay,bx,by;

ax = x0 + b * mult;

bx = x0 - b * mult;

ay = y0 - a * mult;

by = y0 + a * mult;

puts ("2 points");

cout << ax << ' ' << ay << '\n' << bx << ' ' << by << '\n';

}

C# solution

brouillon automatique, à relire avant soumission

using System;
using System.Collections.Generic;
using System.Linq;

public static class AlgorithmDraft
{
    // Auto-generated C# draft from the original e-maxx C/C++ listing. Review before production use.
    |C|
    ----------
    sqrt(A2+B2)
            A C
    x0 = - -----
           A2+B2
            B C
    y0 = - -----
           A2+B2
                      C2
    d = sqrt ( r2 - ----- )
                    A2+B2
                    d2
    mult = sqrt ( ----- )
                  A2+B2
    ax = x0 + B mult
    ay = y0 - A mult
    bx = x0 - B mult
    by = y0 + A mult
    double r, a, b, c; // входные данные
    double x0 = -a*c/(a*a+b*b),  y0 = -b*c/(a*a+b*b);
    if (c*c > r*r*(a*a+b*b)+EPS)
            puts ("no points");
    else if (abs (c*c - r*r*(a*a+b*b)) < EPS) {
            puts ("1 point");
            Console.WriteLine( x0 << ' ' << y0 << '\n';
    }
    else {
            double d = r*r - c*c/(a*a+b*b);
            double mult = sqrt (d / (a*a+b*b));
            double ax,ay,bx,by;
            ax = x0 + b * mult;
            bx = x0 - b * mult;
            ay = y0 - a * mult;
            by = y0 + a * mult;
            puts ("2 points");
            Console.WriteLine( ax << ' ' << ay << '\n' << bx << ' ' << by << '\n';
    }
}

C++ solution

correspondant/original

|C|
----------
sqrt(A2+B2)
        A C
x0 = - -----
       A2+B2
        B C
y0 = - -----
       A2+B2
                  C2
d = sqrt ( r2 - ----- )
                A2+B2
                d2
mult = sqrt ( ----- )
              A2+B2
ax = x0 + B mult
ay = y0 - A mult
bx = x0 - B mult
by = y0 + A mult
double r, a, b, c; // входные данные
double x0 = -a*c/(a*a+b*b),  y0 = -b*c/(a*a+b*b);
if (c*c > r*r*(a*a+b*b)+EPS)
        puts ("no points");
else if (abs (c*c - r*r*(a*a+b*b)) < EPS) {
        puts ("1 point");
        cout << x0 << ' ' << y0 << '\n';
}
else {
        double d = r*r - c*c/(a*a+b*b);
        double mult = sqrt (d / (a*a+b*b));
        double ax,ay,bx,by;
        ax = x0 + b * mult;
        bx = x0 - b * mult;
        ay = y0 - a * mult;
        by = y0 + a * mult;
        puts ("2 points");
        cout << ax << ' ' << ay << '\n' << bx << ' ' << by << '\n';
}

Java solution

brouillon automatique, à relire avant soumission

import java.util.*;
import java.math.*;

public class AlgorithmDraft {
    // Auto-generated Java draft from the original e-maxx C/C++ listing. Review before production use.
    |C|
    ----------
    sqrt(A2+B2)
            A C
    x0 = - -----
           A2+B2
            B C
    y0 = - -----
           A2+B2
                      C2
    d = sqrt ( r2 - ----- )
                    A2+B2
                    d2
    mult = sqrt ( ----- )
                  A2+B2
    ax = x0 + B mult
    ay = y0 - A mult
    bx = x0 - B mult
    by = y0 + A mult
    double r, a, b, c; // входные данные
    double x0 = -a*c/(a*a+b*b),  y0 = -b*c/(a*a+b*b);
    if (c*c > r*r*(a*a+b*b)+EPS)
            puts ("no points");
    else if (abs (c*c - r*r*(a*a+b*b)) < EPS) {
            puts ("1 point");
            System.out.println( x0 << ' ' << y0 << '\n';
    }
    else {
            double d = r*r - c*c/(a*a+b*b);
            double mult = sqrt (d / (a*a+b*b));
            double ax,ay,bx,by;
            ax = x0 + b * mult;
            bx = x0 - b * mult;
            ay = y0 - a * mult;
            by = y0 + a * mult;
            puts ("2 points");
            System.out.println( ax << ' ' << ay << '\n' << bx << ' ' << by << '\n';
    }
}

Материал разбит как Algorithmeическая Problème: изучить постановку, понять асимптотику и реализовать Algorithme на выбранном языке.

Vacancies for this task

offres actives with overlapping task tags are affichés.

Toutes les offres

Il n'y a pas encore d'offres actives.