Universal Cup Judging System

Universal Cup

حد الوقت: 2.0 s حد الذاكرة: 1024 MB مجموع النقاط: 100 الصعوبة: [عرض] قابلة للهجوم ✓
الإحصائيات

Arona muốn giành chức vô địch khu vực (regional championship). Vì vậy, Plana đã tạo ra bài toán sau cho Arona dựa trên từ khóa "miền" (region).

Cho ba số nguyên $n$, $m$ và $k$, bạn cần vẽ $n$ đường tròn, $m$ hình tam giác và $k$ đường thẳng trên một mặt phẳng để chia mặt phẳng đó thành nhiều miền nhất có thể.

Tất nhiên, kỹ năng vẽ và khả năng toán học của Arona rất kém. Vì vậy cô ấy tìm đến bạn để nhờ giúp đỡ.

Dữ liệu vào

Có nhiều bộ dữ liệu. Dòng đầu tiên của đầu vào chứa một số nguyên $T$ ($1 \le T \le 5 \times 10^3$) cho biết số lượng bộ dữ liệu. Đối với mỗi bộ dữ liệu:

Dòng đầu tiên và duy nhất chứa ba số nguyên $n$, $m$ và $k$ ($0 \le n, m, k \le 100$, $n + m + k > 0$) cho biết số lượng đường tròn, hình tam giác và đường thẳng.

Dữ liệu đảm bảo tổng của $(\max(n, m, k))^3$ trong tất cả các bộ dữ liệu không vượt quá $10^7$.

Dữ liệu ra

Đối với mỗi bộ dữ liệu:

Đầu tiên, in ra một dòng chứa một số nguyên, cho biết số lượng miền tối đa có thể chia được.

Sau đó in ra $n$ dòng. Mỗi dòng chứa ba số nguyên $x$, $y$ và $R$ ($-10^3 \le x, y \le 10^3$, $1 \le R \le 10^3$) cách nhau bởi một dấu cách, biểu thị tọa độ tâm và bán kính của đường tròn.

Tiếp theo, in ra $m$ dòng. Mỗi dòng chứa sáu số nguyên $x_1$, $y_1$, $x_2$, $y_2$, $x_3$ và $y_3$ ($-10^3 \le x_1, y_1, x_2, y_2, x_3, y_3 \le 10^3$, $(x_1, y_1) \ne (x_2, y_2)$, $(x_1, y_1) \ne (x_3, y_3)$, $(x_2, y_2) \ne (x_3, y_3)$) cách nhau bởi một dấu cách, biểu thị tọa độ ba đỉnh của hình tam giác.

Cuối cùng, in ra $k$ dòng. Mỗi dòng chứa bốn số nguyên $x_1$, $y_1$, $x_2$ và $y_2$ ($-10^3 \le x_1, y_1, x_2, y_2 \le 10^3$, $(x_1, y_1) \ne (x_2, y_2)$) cách nhau bởi một dấu cách, biểu thị tọa độ của hai điểm nằm trên đường thẳng.

Có thể chứng minh rằng, ngay cả với các giới hạn được nêu ở trên, ta luôn có thể đạt được đáp án tối ưu.

Ví dụ

3
1 0 1
0 1 1
1 1 2
4
0 0 1
-2 0 2 0
4
0 0 0 2 2 0
0 1 1 0
18
3 4 2
2 7 2 1 6 4
3 4 6 4
3 3 3 5

Ghi chú

Bộ dữ liệu ví dụ thứ ba được minh họa ở dưới đây.

problem_14812_478e31d2dc02ec2ad85e008d91ad27d7.png
problem_14812_c49174cf27c03ed0f97fb330c3e4891b.png

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.