Processing math: 94%
Solutions of Line segment intersection - MarisaOJ: Marisa Online Judge

Solutions of Line segment intersection

Select solution language

Write solution here.


User Avatar noice    Created at    2 likes

## Bài toán yêu cầu bạn xem có tồn tại giao điểm giữa hai đoạn thẳng ABCD hay không. ## Một hướng giải là xác định vị trí tương đối của một bộ 3 điểm trong không gian, từ đó sẽ tìm được cách bố trí của các đoạn thẳng. Có thể giải như sau: - Như bạn đã biết -- Trong không gian 2 chiều, 3 điểm phân biệt có thể thẳng hàng hoặc không, nhưng cũng có thể sắp xếp **cùng chiều kim đồng hồ** hoặc **ngược chiều kim đồng hồ**. Khái niệm mở rộng này sẽ là tư tưởng của lời giải. - Khi bạn xét 3 điểm P(px,py), Q(qx,qy), và R(rx,ry) phân biệt, hướng của đường đi gấp khúc PQR có thể được xác định qua công thức: s(P,Q,R)=(qxpx)(ryqy)(qypy)(rxqx). - - Nếu s(P,Q,R)=0 thì P, QR thẳng hàng. - Nếu s(P,Q,R)>0 thì P, QR tạo thành đường đi ngược chiều kim đồng hồ. - Nếu s(P,Q,R)<0 thì P, QR tạo thành đường đi cùng chiều kim đồng hồ. *(thực chất công thức cũng cho bạn biết vị trí của điểm R so với đường thẳng PQ)* - Từ đó bạn rút ra nhận xét: - Nếu AB nằm khác phía đối với đường thẳng CD, đồng thời CD nằm khác phía đối với đường thẳng AB thì hai đoạn ABCD giao nhau. - Hai đoạn ABCD cũng được coi là giao nhau nếu ít nhất một đầu mút của đoạn này nằm trên đoạn kia. - Công thức mấu chốt của lời giải một phần có liên quan đến **tích vector vô hướng**, bạn có thể đọc thêm ở [đây](https://wiki.vnoi.info/algo/geometry/basic-geometry-2). ### Code tham khảo: #clude<bitsstdc++.h>usingnamespacestd;#defelonglong#defenlnstate(px,py,qx,qy,rx,ry){val=(qx-px)(ry-qy)-(qy-py)(rx-qx);if