Cho N tam giác được cho bởi toạ độ các đỉnh Ai(x,y), Bi(x,y), Ci(x,y), (i=1..N,2<=N<=1000). Tam giác i được gọi là bao tam giác j nếu 3 đỉnh của tam giác j đều thuộc miền trong của tam giác i. Hãy tìm dãy các tam giác bao nhau có số lượng lớn nhất?
Dữ liệu vào: Dòng đầu ghi số N; Trong N dòng tiếp theo dòng thứ i+1 ghi toạ độ 3 đỉnh của tam giác thứ i. Toạ độ nguyên dương <=106
Kết quả ra: Ghi số lượng tam giác bao nhau lớn nhất. Trường hợp không có dãy các tam giác bao nhau ghi số 0.
Ví dụ:
|
DTAMGIAC.INP |
DTAMGIAC.OUT |
Giải thích |
|
5 1 1 14 1 1 7 2 3 7 3 2 9 5 1 3 4 8 2 -4 2 2 5 8 3 7 6 9 8 9 2 |
2
|
có 2 tam giác bao nhau có các tọa độ là: 5 1 3 4 8 2 1 1 14 1 1 7 |