LQDOJ CUP 2022 - Round 7 - TRICOVER

Xem PDF

Điểm: 100 (p) Thời gian: 10.0s Bộ nhớ: 512M Input: TRICOVER.inp Output: TRICOVER.out

Quis vừa phát minh ra một robot cắt cỏ mới. Nó sử dụng trí tuệ nhân tạo để đưa ra quyết định là nên cắt ở đâu, diện tích bao nhiêu. Tuy nhiên, đáng buồn là do chưa đủ dữ liệu nên hiện tại robot chỉ có thể cắt một cách vô cùng ngẫu nhiên, hiệu suất không cao.

Trong hôm nay, robot đã cắt được \(n\) vùng trên bãi cỏ. Ta có thể coi bãi cỏ là một hình chữ nhật trên mặt phẳng, có độ dài bề ngang và bề dọc lần lượt là \(W\)\(H\) đơn vị. Để dễ xác định vị trí mà robot đã cắt, ta đặt gốc tọa độ \(Oxy\) ở góc trái dưới của hình chữ nhật sao cho hai trục \(Ox\), \(Oy\) trùng với cạnh của hình chữ nhật.

Do cấu tạo đặc biệt, mỗi lần cắt cỏ, robot sẽ cắt toàn bộ cỏ trong một hình tam giác có tọa độ các đỉnh nguyên và nằm gọn trong bãi cỏ.

Nhằm đánh giá hiệu suất của buổi cắt cỏ ngày hôm nay (với \(n\) vùng đã được cắt), làm cơ sở để robot điều chỉnh và học tập, hãy tính diện tích trung bình mỗi lần cắt, được tính bằng cách lấy tổng diện tích cỏ đã được cắt, chia cho \(n\).

Input

  • Dòng đầu tiên chứa ba số nguyên \(n\), \(W\)\(H\) (\(1 \le n \le 300\), \(1\le W, H \le 10^4\)) lần lượt là là số vùng cắt và kích thước bãi cỏ.
  • Trong \(n\) dòng tiếp theo, mỗi dòng chứa sáu số nguyên \(x_1\), \(y_1\), \(x_2\), \(y_2\), \(x_3\)\(y_3\) (\(0 \leq x_1, x_2, x_3 \leq W\), \(0 \leq y_1, y_2, y_3 \leq H\)), trong đó \((x_1, y_1)\), \((x_2, y_2)\), \((x_3, y_3)\) là tọa độ các đỉnh của vùng được cắt.
  • Dữ liệu đảm bảo không có ba điểm nào thẳng hàng và các đỉnh có tọa độ phân biệt.

Output

  • Một dòng duy nhất chứa một số thực là hiệu suất tính được.

Note

  • Đáp án của bạn được coi là đúng nếu như chênh lệch giữa nó với đáp án của giám khảo không vượt quá \(10^{-6}\).
  • Cụ thể, giả sử bạn đưa ra số \(a\), đáp án của test đó là \(b\) thì bạn đúng được test này khi và chỉ khi \(\frac{|a-b|}{\max(a,b)} \leq 10^{-6}\).

Scoring

  • Subtask \(1\) (\(5\%\) số điểm): \(n = 1\).
  • Subtask \(2\) (\(30\%\) số điểm): \(n \leq 14\).
  • Subtask \(3\) (\(25\%\) số điểm): Các tam giác là tam giác vuông cân có hai cạnh song song với trục tọa độ, và chỉ thuộc vào một trong hai dạng sau:

  • Subtask \(4\) (\(40\%\) số điểm): Không có ràng buộc gì thêm.

Example

Test 1

Input
1 5 5
0 0 3 0 0 4
Output
6.000000152004
Note

Chỉ có một hình tam giác duy nhất là tam giác vuông có hai cạnh góc vuông lần lượt là \(3\)\(4\), diện tích của hình là \(6\). Vì \(6.00000152004\) có sai số tương đối nhỏ hơn \(10^{-6}\) nên đáp án được chấp nhận.

Test 2

Input
3 10 10
6 10 4 4 2 10
1 0 10 7 5 4
1 1 9 1 0 8
Output
13.9219260464
Note

Dưới đây là hình minh họa:


Bình luận

Không có bình luận nào.