Đây chỉ là một ý tưởng và nó có thể không thành công. :V
==============================
Python 3.
Cần chuẩn bị thư viện Shapely. Nếu chưa có thì bạn dùng lệnh sau để tải về:
pip install shapely
==============================
Bước 1: Đọc dữ liệu trong file GOOD.INP:
+ Đọc theo thứ tự x trước y sau lưu vào hai dictionary X và Y
+Ví dụ: X = {'tg1':[0, 0, 1, 1, 0.5]} và Y = {'tg1':[0, 1, 1, 0, 0.5]}
Bước 2: Tìm tam giác độc lập.
+ tg1 = Polygon([A, B, C])
tg2 = Polygon([A, B, C])
kt = tg1.intersects(tg2)
Nếu 2 tam giác giao nhau thì kt sẽ là true và không giao sẽ là false.
+ Nếu giao nhau thì tìm cạnh giao nhau, nếu không có cạnh giao nhau thì hai tam giác này lồng vào nhau, thì hai tam giác đó là độc lập.
Bước 3: Tính diện tích S = 0.5*abs((xB-xA)*(yC-yA)-(xC-xA)*(yB-yA))
Bước 4: Gán giá trị của S cho Max nếu Max < S. Sau đó quay lại bước hai cho đên khi hết tam giác độc lập.
Bước 5: Tìm tam giác giao nhau.
+ tg1 = Polygon([A, B, C])
tg2 = Polygon([A, B, C])
kt = tg1.intersects(tg2)
Nếu 2 tam giác giao nhau thì kt sẽ là true và không giao sẽ là false.
+ Nếu giao nhau thì tìm cạnh giao nhau, nếu không có cạnh giao nhau thì hai tam giác này lồng vào nhau, thì thì hai tam giác này không giao nhau.
Bước 6: Xác định tọa độ giao điểm của cạnh cắt nhau.
+d1 = LineString([(x1, y1), (x2, y2)])
d2 = LineString([(x3, y3), (x4, y4)])
p = d1.intersection(d2)
p_giaodiem = p.x, p.y
Bước 7: Tính diện tích đa giác đó.
+def polygonArea(X, Y, n): #polygon: đa giác, polygonArea: diện tích đa giác.
area = 0.0
j = n - 1
for i in range(0,n):
area += (X[j] + X[i]) * (Y[j] - Y[i])
j = i
return abs(area / 2.0)
P/S: Phần code trên được mình lấy từ trang geeksforgeeks, do mình chưa viết đuọc đoạn code tính đa giác.
Bước 8: Gán giá trị của S cho Max nếu Max < S. Sau đó quay lại bước 5 cho đên khi hết tam giác giao nhao.
Bước 9: In Max ra file GOOD.OUT.
Bước 10: Đi ngủ. :))
