Seqmentlərin kəsişməsi#839

Seqmentlərin kəsişməsi (Həll təhlili)

Bir fiqurun məhdudlaşdırıcı düzbucaqlısı — koordinat oxlarına paralel olan və verilmiş fiquru tamamilə əhatə edən ən kiçik düzbucaqlıdır.

Sadə şəkildə desək, əgər biz fiquru elə "düzbucağa yerləşdirmək" istəyiriksə ki, onun bütün nöqtələri içəridə olsun, məhdudlaşdırıcı düzbucaq minimal ölçüdə olacaq.

$(x_{1}, y_{1})$ (x_1, y_1) və $(x_{2}, y_{2})$ (x_2, y_2) nöqtələrində sonlanan bir xətti nəzərdən keçirək. Onun məhdudlaşdırıcı düzbucağını tapmaq üçün:

Düzbucağın sol aşağı küncünü təyin edək:

x_{1}^{'} = min (x_{1}, x_{2}), y_{1}^{'} = min (y_{1}, y_{2})

x_1' = min(x_1, x_2), y_1' = min(y_1, y_2)

Düzbucağın sağ yuxarı küncünü təyin edək:

x_{2}^{'} = ma x (x_{1}, x_{2}), y_{2}^{'} = ma x (y_{1}, y_{2})

x_2' = max(x_1, x_2), y_2' = max(y_1, y_2)

Beləliklə, məhdudlaşdırıcı düzbucaq bizim xəttimizə daxil olan $(x_{1}^{'}, y_{1}^{'})$ (x_1', y_1') və $(x_{2}^{'}, y_{2}^{'})$ (x_2', y_2') bucaqlara malik olan düzbucaqdır.

Lema. Tutaq ki, düz üzərində iki xətt $(x_{1}, x_{2})$ (x_1, x_2) və $(x_{3}, x_{4})$ (x_3, x_4) verilib, burada $x_{1} < x_{2}$ x_1 < x_2 və $x_{3} < x_{4}$ x_3 < x_4. Xəttlər nə zaman və yalnız nə zaman kəsişməzlər ki, ya birinci xətt ikinciyə nisbətən sol tərəfdə yerləşir, ya da ikinci birincinin sol tərəfində yerləşir.

Lema. Tutaq ki, müstəvidə iki düzbucaq verilmişdir $(x_{1}, y_{1}) - (x_{2}, y_{2})$ (x_1, y_1) - (x_2, y_2) və $(x_{3}, y_{3}) - (x_{4}, y_{4})$ (x_3, y_3) - (x_4, y_4), burada $x_{1} < x_{2}, y_{1} < y_{2}$ x_1 < x_2, y_1 < y_2 və $x_{3} < x_{4}, y_{3} < y_{4}$ x_3 < x_4, y_3 < y_4. Düzbucaqlar nə zaman və yalnız nə zaman kəsişməzlər ki, ya $(x_{1}, x_{2})$ (x_1, x_2) və $(x_{3}, x_{4})$ (x_3, x_4) xəttlərin kəsişməzlər, ya da $(y_{1}, y_{2})$ (y_1, y_2) və $(y_{3}, y_{4})$ (y_3, y_4) xəttlərin kəsişməzlər.

İki xəttin kəsişmə meyarı

İki xətt $A B$ və $C D$ nə zaman və yalnız nə zaman kəsişir ki, üç şərt təmin olunur:

1. Məhdudlaşdırıcı düzbucaqlar kəsişir.

2. $C$ və $D$ nöqtələri $A B$ düz xəttin əks tərəflərində yerləşir və ya ən azı $C$ və ya $D$ nöqtəsi $A B$ xəttində yerləşir. Bu o deməkdir ki,

[A B \times A C] \cdot [A B \times A D] \leq 0

[AB \times AC] \cdot [AB \times AD] \le 0

3. $A$ və $B$ nöqtələri $C D$ düz xəttin əks tərəflərində yerləşir və ya ən azı $A$ və ya $B$ nöqtəsi $C D$ xəttində yerləşir. Bu o deməkdir ki,

[C D \times C A] \cdot [C D \times C B] \leq 0

[CD \times CA] \cdot [CD \times CB] \le 0

Aşağıda iki xəttin müxtəlif qarşılıqlı yerləşmə halları və onlara uyğun olan vektor çoğrafi vurma qiymətləri verilib.

Növbəti nümunədə hər bir xətt digər xətti olan xətti əhatə edən xətti kəsir. Lakin onların məhdudlaşdırıcı düzbucaqları kəsişmir.

Nümunə

Birinci nümunədə xəttlər kəsişir. İkinci nümunədə isə kəsişmir.

Alqoritmın həyata keçirilməsi

Xəttlərin uclarının koordinatları tam ədədlər olduğuna görə, hesablamalarda yalnız tam ədəd tipi long long istifadə edəcəyik. Gələcəkdə bizə $n$ sayının işarəsini müəyyən edən sgn funksiyası lazım olacaq.

int sgn(long long n)
{
  return (n > 0) - (n < 0);
}

RectanglesIntersects funksiyası $A B$ və $C D$ xətti üçün məhdudlaşdırıcı düzbucaqların koordinatlarını arqument olaraq qəbul edir. Əgər $(x_{1}, y_{1}) - (x_{2}, y_{2})$ (x_1, y_1) - (x_2, y_2) və $(x_{3}, y_{3}) - (x_{4}, y_{4})$ (x_3, y_3) - (x_4, y_4) düzbucaqları kəsişirsə $1$ , əks halda $0$ qaytarır.

int RectanglesIntersect(long long x1, long long y1, 
                        long long x2, long long y2,
                        long long x3, long long y3, 
                        long long x4, long long y4)
{
  if (sgn(x3 - x2) * sgn(x4 - x1) > 0) return 0;
  if (sgn(y3 - y2) * sgn(y4 - y1) > 0) return 0;
  return 1;
}

C++

cross funksiyası $(A_{x}, A_{y})$ (A_x, A_y) və $(B_{x}, B_{y})$ (B_x, B_y) iki vektorun vektor fəza vurmasını hesablayır.

long long cross(long long Ax, long long Ay, 
                long long Bx, long long By)
{
  return Ax * By - Ay * Bx;
}

intersect funksiyası $A B$ və $C D$ xətti arasında kəsişmə olub olmadığını yoxlayır.

int segmentsIntersect(long long x1, long long y1, 
                      long long x2, long long y2,
                      long long x3, long long y3,
                      long long x4, long long y4)
{

Məhdudlaşdırıcı düzbucaqların kəsişməsini yoxlayırıq. Əgər kəsişmirlərsə, $0$ qaytarırıq.

  if (!RectanglesIntersect(
       min(x1, x2), min(y1, y2), max(x1, x2), max(y1, y2),
       min(x3, x4), min(y3, y4), max(x3, x4), max(y3, y4))
     ) return 0;

$A B, A C, A D$ AB, AC, AD vektorlarını qururuq.

  long long ABx = x2 - x1, ABy = y2 - y1;
  long long ACx = x3 - x1, ACy = y3 - y1;
  long long ADx = x4 - x1, ADy = y4 - y1;

$C D, C A, C B$ CD, CA, CB vektorlarını qururuq.

  long long CDx = x4 - x3, CDy = y4 - y3;
  long long CAx = x1 - x3, CAy = y1 - y3;
  long long CBx = x2 - x3, CBy = y2 - y3;

Vektor fəza vurmalarını hesablayırıq.

  long long ABxAC = cross(ABx, ABy, ACx, ACy); // AB x AC
  long long ABxAD = cross(ABx, ABy, ADx, ADy); // AB x AD
  long long CDxCA = cross(CDx, CDy, CAx, CAy); // CD x CA
  long long CDxCB = cross(CDx, CDy, CBx, CBy); // CD x CB

Segmentlərin kəsişmə meyarının $2$ və $3$ punktlarını yoxlayırıq. Əgər yerinə yetirilməzsə, $0$ qaytarırıq. Ehtiyat üçün, artıqzamanları qarşısını almaq üçün, ədədlərin işarələrinin çarpımını nətlə müqayisə etmək lazımdır.

  if (sgn(ABxAC) * sgn(ABxAD) > 0) return 0;
  if (sgn(CDxCA) * sgn(CDxCB) > 0) return 0;
  return 1; // Xəttlər kəsişir
}

Programın əsas hissəsi. Giriş məlumatlarını oxuyuruq.

scanf("%lld %lld %lld %lld",&x1,&y1,&x2,&y2);
scanf("%lld %lld %lld %lld",&x3,&y3,&x4,&y4);

Xəttlərin kəsişməsini yoxlayırıq.

if (segmentsIntersect(x1, y1, x2, y2, x3, y3, x4, y4))
  puts("Yes");
else
  puts("No");