Solutions of Segment - MarisaOJ: Marisa Online Judge

Solutions of Segment

Select solution language

Write solution here.


tungtungtungsahur    Created at    0 likes

Gọi đoạn [a,b] là AB, [c,d] là CD. Nếu như cả bốn điểm A, B, C, D đều không cùng nằm trên cả hai đoạn AB và CD(+) thì hai đoạn thẳng này rời nhau hoàn toàn. Thật vậy, ta xét trường hợp (+): + Nếu C nằm bên trái AB, hiển nhiên D phải nằm bên trái AB vì nếu D nằm bên trái AB, điểm A và B sẽ vừa nằm trên AB vừa nằm trên CD, mâu thuẫn (+). Do cả C và D đều nằm bên trái AB nên đoạn AB và đoạn CD rời nhau hoàn toàn. + Nếu C nằm bên phải AB thì D cũng nằm bên phải AB, do đó hai đoạn AB và CD rời nhau hoàn toàn. Vậy để hai đoạn thẳng này có điểm chung thì ít nhất một trong 4 điểm A, B, C, D cùng nằm trên cả hai đoạn AB và CD. Và ngược lại: một trong 4 điểm A, B, C, D cùng nằm trên cả hai đoạn AB và CD thì hai đoạn này có ít nhất một điểm chung. Đến đây, ta chỉ cần chia ra 4 trường hợp: A thuộc CD, B thuộc CD, C thuộc AB, D thuộc AB và tìm điều kiện tương ứng của a, b, c, d (Ví dụ: A thuộc CD thì nghĩa là c<=a<=d).