Universal Cup Judging System

Universal Cup

Time Limit: 2.0 s Memory Limit: 1024 MB Total points: 100 Difficulty: [show] Hackable ✓
Statistics

Arona 想要贏得區域賽冠軍。於是 Plana 根據關鍵字「區域」為 Arona 出了以下問題。

給定三個整數 $n$、$m$ 與 $k$,你需要在平面上畫出 $n$ 個圓、$m$ 個三角形與 $k$ 條直線,將平面分割成盡可能多的區域。

當然,Arona 的繪畫技巧與數學能力都非常差。因此她來向你求助。

輸入格式

有多組測試資料。輸入的第一行包含一個整數 $T$($1 \le T \le 5 \times 10^3$),代表測試資料的組數。對於每組測試資料:

第一行也是唯一的一行包含三個整數 $n$、$m$ 與 $k$($0 \le n, m, k \le 100$,$n + m + k > 0$),分別代表圓、三角形與直線的數量。

保證所有測試資料中 $(\max(n, m, k))^3$ 的總和不超過 $10^7$。

輸出格式

對於每組測試資料:

首先,輸出一行包含一個整數,代表最多能分割出的區域數量。

接著輸出 $n$ 行。每行包含三個以空格分隔的整數 $x$、$y$ 與 $R$($-10^3 \le x, y \le 10^3$,$1 \le R \le 10^3$),代表圓心的座標以及圓的半徑。

再接著輸出 $m$ 行。每行包含六個以空格分隔的整數 $x_1$、$y_1$、$x_2$、$y_2$、$x_3$ 與 $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)$),代表三角形三個頂點的座標。

最後輸出 $k$ 行。每行包含四個以空格分隔的整數 $x_1$、$y_1$、$x_2$ 與 $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)$),代表直線上兩點的座標。

可以證明,即使在上述範圍限制下,我們也總是能達到最佳解。

範例

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

說明

第三組範例測試資料如下圖所示。

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.