Хоёр тойргийн нийтлэг шүргэгчийг олох¶

Хоёр тойрог өгөгдсөн. Тэдгээрийн бүх нийтлэг шүргэгчийг, өөрөөр хэлбэл хоёр тойргийг зэрэг шүргэдэг бүх шулууныг олох шаардлагатай.

Тайлбарласан алгоритм нэг (эсвэл хоёулаа) тойрог цэг болж хувирах тохиолдолд ч ажиллана. Ингэснээр энэ алгоритмыг өгөгдсөн цэгээр дайрсан тойргийн шүргэгчийг олоход мөн ашиглаж болно.

Нийтлэг шүргэгчийн тоо¶

Хоёр тойргийн нийтлэг шүргэгчийн тоо 0,1,2,3,4 ба төгсгөлгүй байж болно. Өөр өөр тохиолдлын зургуудыг үз.

Хоёр тойргийн нийтлэг шүргэгчийн өөр өөр тохиолдол

Энд бид degenerate case-үүдийг авч үзэхгүй, өөрөөр хэлбэл тойргууд давхцах (энэ тохиолдолд тэдгээр төгсгөлгүй олон нийтлэг шүргэгчтэй), эсвэл нэг тойрог нөгөөгийнхөө дотор орших (энэ тохиолдолд тэдгээр нийтлэг шүргэгчгүй, эсвэл тойргууд шүргэлцэж байвал нэг нийтлэг шүргэгчтэй) тохиолдлыг.

Ихэнх тохиолдолд хоёр тойрог дөрвөн нийтлэг шүргэгчтэй байна.

Хэрэв тойргууд шүргэлцэж байвал тэдгээр гурван нийтлэг шүргэгчтэй байх боловч үүнийг degenerate case гэж ойлгож болно: хоёр шүргэгч давхцсан мэт.

Түүнчлэн доор тайлбарласан алгоритм нэг эсвэл хоёр тойрог тэг радиустай байх тохиолдолд ажиллана: энэ тохиолдолд харгалзан хоёр эсвэл нэг нийтлэг шүргэгч байх болно.

Дүгнэвэл бид төгсгөлгүй олон шүргэгчтэй тохиолдлоос бусад бүх тохиолдолд үргэлж дөрвөн шүргэгч хайх болно (Төгсгөлгүй олон шүргэгчтэй тохиолдлыг тусад нь боловсруулах шаардлагатай бөгөөд үүнийг энд авч үзээгүй). degenerate case-үүдэд зарим шүргэгч давхцах боловч эдгээр тохиолдол ч мөн ерөнхий дүр зурагт багтана.

Алгоритм¶

Алгоритмыг хялбар болгохын тулд бид ерөнхий чанараа алдалгүйгээр эхний тойргийн төв $(0, 0)$ координаттай гэж үзнэ. (Хэрэв тийм биш бол үүнийг зүгээр л бүх зургийг шилжүүлж, шийдийг олсны дараа гарсан шулуунуудыг буцааж шилжүүлэх замаар хийж болно.)

$r_1$ ба $r_2$-оор эхний ба хоёр дахь тойргийн радиусыг, $(v_x,v_y)$-ээр хоёр дахь тойргийн төвийн координат ба эх цэгээс ялгаатай $v$ цэгийг тэмдэглэе. (Тэмдэглэл: бид хоёр тойрог ижил байх тохиолдлыг авч үзэхгүй).

Бодлогыг бодохын тулд бид түүнд цэвэр алгебрийн аргаар хандана. Бид координатын эх цэгээс $r_1$ зайд, $v$ цэгээс $r_2$ зайд орших $ax + by + c = 0$ хэлбэрийн бүх шулууныг олох хэрэгтэй. Түүнчлэн бид шулууны нормчлолын нөхцөлийг тавина: коэффициентүүдийн квадратуудын нийлбэр нэгтэй тэнцүү байх ёстой (энэ нь зайлшгүй шаардлагатай, эс бөгөөс ижил шулуунд $ax + by + c = 0$ хэлбэрийн төгсгөлгүй олон илэрхийлэл харгалзана). Нийтдээ бид хайж буй $a, b, c$-ийн хувьд дараах тэгшитгэлийн системийг авна:

$$\begin{align} a^2 + b^2 &= 1 \\ \mid a \cdot 0 + b \cdot 0 + c \mid &= r_1 \\ \mid a \cdot v_x + b \cdot v_y + c \mid &= r_2 \end{align}$$

Модулиас салахын тулд энэ системд модулийг задлах ердөө дөрвөн арга байгааг анхаарна уу. Хэрэв бид модулийг задлахыг баруун талын коэффициентийг -1-ээр үржүүлж болно гэж ойлговол эдгээр бүх аргыг ерөнхий тохиолдлоор авч үзэж болно. Өөрөөр хэлбэл бид дараах систем рүү шилжинэ:

$$\begin{align} a^2 + b^2 &= 1 \\ c &= \pm r_1 \\ a \cdot v_x + b \cdot v_y + c &= \pm r_2 \end{align}$$

$d_1 = \pm r_1$ ба $d_2 = \pm r_2$ тэмдэглэгээг оруулснаар бид систем дөрвөн шийдтэй байх ёстой гэсэн дүгнэлтэд хүрнэ:

$$\begin{align} a^2 + b^2 &= 1 \\ c &= d_1 \\ a \cdot v_x + b \cdot v_y + c &= d_2 \end{align}$$

Энэ системийн шийд нь квадрат тэгшитгэл бодох болтол хураагдана. Бид бүх төвөгтэй тооцооллыг орхиж, бэлэн хариултыг шууд өгнө:

$$\begin{align} a &= {( d_2 - d_1 ) v_x \pm v_y \sqrt{v_x^2 + v_y^2-(d_2-d_1)^2} \over {v_x^2 + v_y^2} } \\ b &= {( d_2 - d_1 ) v_y \pm v_x \sqrt{v_x^2 + v_y^2-(d_2-d_1)^2} \over {v_x^2 + v_y^2} } \\ c &= d_1 \end{align}$$

Нийтдээ бид дөрвний оронд найман шийд авлаа. Гэвч илүүдэл шийд хаанаас үүсдэгийг ойлгоход амархан: үнэндээ сүүлийн системд зөвхөн нэг шийдийг (жишээ нь эхнийхийг) авахад хангалттай. Үнэндээ бид $\pm r_1$ ба $\pm r_2$-г авч байгаагийн геометрийн утга тодорхой: бид тойрог бүрийн аль талд шулуун байгааг үнэндээ ялгаж байгаа юм. Тиймээс сүүлийн системийг бодохад үүсэх хоёр арга илүүдэл юм: хоёр шийдийн нэгийг сонгоход хангалттай (зөвхөн мэдээж дөрвөн тохиолдолд бүгдэд нь ижил шийдийн бүлийг сонгох ёстой).

Бидний хараахан авч үзээгүй сүүлчийн зүйл бол эхний тойрог анх эх цэгт байрлаагүй тохиолдолд шулуунуудыг хэрхэн шилжүүлэх явдал юм. Гэвч энд бүх зүйл энгийн: шулууны тэгшитгэлийн шугаман чанараас $a \cdot x_0 + b \cdot y_0$ утгыг ($x_0$ ба $y_0$ нь эхний тойргийн анхны төвийн координат) $c$ коэффициентээс хасах ёстой нь гарна.

Implementation¶

We first describe all the necessary data structures and other auxiliary definitions:

struct pt {
    double x, y;

    pt operator- (pt p) {
        pt res = { x-p.x, y-p.y };
        return res;
    }
};

struct circle : pt {
    double r;
};

struct line {
    double a, b, c;
};

const double EPS = 1E-9;

double sqr (double a) {
    return a * a;
}

Then the solution itself can be written this way (where the main function for the call is the second; and the first function is an auxiliary):

void tangents (pt c, double r1, double r2, vector<line> & ans) {
    double r = r2 - r1;
    double z = sqr(c.x) + sqr(c.y);
    double d = z - sqr(r);
    if (d < -EPS)  return;
    d = sqrt (abs (d));
    line l;
    l.a = (c.x * r + c.y * d) / z;
    l.b = (c.y * r - c.x * d) / z;
    l.c = r1;
    ans.push_back (l);
}

vector<line> tangents (circle a, circle b) {
    vector<line> ans;
    for (int i=-1; i<=1; i+=2)
        for (int j=-1; j<=1; j+=2)
            tangents (b-a, a.r*i, b.r*j, ans);
    for (size_t i=0; i<ans.size(); ++i)
        ans[i].c -= ans[i].a * a.x + ans[i].b * a.y;
    return ans;
}

Бодлогууд¶

TIMUS 1163 Chapaev