Editorial for Tứ giác

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Yunan

Có tổng cộng $6$ ~6~ cặp điểm, ta kiểm tra xem mỗi cặp điểm có phải là đường chéo của tứ giác lồi hay không.

Xét cặp điểm $(p_1,p_2)$ ~(p_1,p_2)~ cần kiểm tra, cặp điểm còn lại là $(p_3,p_4)$ ~(p_3,p_4)~. Hai cặp điểm này là hai đường chéo của tứ giác lồi khi và chỉ khi:

Không có $3$ ~3~ điểm nào thẳng hàng.
$p_1$ ~p_1~ và $p_2$ ~p_2~ nằm ở hai phía khác nhau so với đường thẳng nối hai điểm $p_3-p_4$ ~p_3-p_4~.
$p_3$ ~p_3~ và $p_4$ ~p_4~ nằm ở hai phía khác nhau so với đường thẳng nối hai điểm $p_1-p_2$ ~p_1-p_2~.

Độ phức tạp: $O(1)$ ~O(1)~ với mỗi test case

Editorial for Tứ giác

Comments