Trên mặt phẳng tọa độ, xét đa giác lồi n đỉnh, các đỉnh đều có tọa độ nguyên và có giá trị tuyệt đối không vượt quá 10^5. Các đỉnh của đa giác được liệt kê theo chiều kim đồng hồ (thuận, nghịch).
Yêu cầu: Cho đoạn thẳng xác định bởi hai điểm có tọa độ là (x1, y1) và (x2, y2) trong đó x1, y1, x2, y2 là các số nguyên và có giá trị tuyệt đối không vượt quá 10^5. Hãy xác định độ dài L là phần của đoạn thẳng nằm trong đa giác hay trên cạnh của đa giác và đưa ra số nguyên là phần nguyên của tích (L * 100).
Dữ liệu vào từ file văn bản “DG.INP” có dạng:
Hai số liên tiếp trên một dòng cách nhau một dấu cách.
Kết quả cho ra file văn bản “DG.OUT” có dạng: ghi một số nguyên là phần nguyên của tích (L * 100).
Ví dụ:
DG.INP |
DG.OUT |
4 0 1 1 0 0 -1 -1 0 -2 0 0 0 |
100 |