Universal Cup Judging System

Universal Cup

Límite de tiempo: 1 s Límite de memoria: 512 MB Puntuación total: 100 Hackeable ✓
Estadísticas

Yuki 係國際凸多邊形錦標賽(ICPC)嘅總裁判。佢為比賽出咗一道幾何題。不過,因為佢缺乏幾何經驗,所以未能產生正確嘅凸多邊形數據。

為咗證明自己嘅幾何能力,Yuki 又開始玩木棒。佢有 $n$ 根木棒,第 $i$ 根嘅長度係 $a_i$。佢打算從中揀至少 $3$ 根,令呢啲木棒可以砌成一個非退化凸多邊形$^*$。

不過,Yuki 對幾何唔係好熟,所以唔知點揀木棒。作為 Yuki 嘅好朋友,你要幫佢搵一個木棒子集,令到:

  • 子集至少有 $3$ 根木棒,而且木棒數量盡可能多;

  • 從呢個子集任揀至少 $3$ 根木棒,呢啲木棒都可以砌成一個非退化凸多邊形。

或者報告冇呢種子集。

$^*$:非退化凸多邊形係指所有邊長都大過零、任意三個頂點唔共線,而且所有內角都嚴格細過 $180^\circ$ 嘅多邊形。

輸入格式

呢題有多組測試數據。

第一行包含一個正整數 $t$($1 \le t \le 10^5$),表示測試數據嘅組數。

對於每組測試數據:

  • 第一行包含一個正整數 $n$($3 \le n \le 5 \cdot 10^5$)。

  • 第二行包含 $n$ 個正整數 $a_1,\ldots,a_n$($1 \le a_i \le 10^9$)。

保證所有測試數據嘅 $n$ 總和唔超過 $5 \cdot 10^5$。

輸出格式

對於每組測試數據,輸出一行:

  • 如果冇呢種子集,輸出一個整數 $0$。

  • 如果有呢種子集,先輸出一個整數 $k$,表示你搵到嘅子集大小,再輸出 $k$ 個整數 $b_1,\ldots,b_k$,表示子集入面呢 $k$ 根木棒嘅長度。

樣例

輸入格式 1

3
4
6 9 2 6
3
4 4 9
6
3 1 4 6 5 9

輸出格式 1

3 6 2 6
0
4 3 4 5 6

說明

對於第一組測試數據:

  • $\{6,2,6\}$ 係合法子集;因為 $2+6>6$,呢 $3$ 根木棒可以砌成非退化三角形;好容易證明冇更大嘅合法子集。

  • $\{6,6,9\}$ 亦都係合法子集。

對於第二組測試數據:

  • 可以證明冇合法子集。

對於第三組測試數據:

  • $\{3,4,5,6\}$ 係合法子集;呢個情況下,Yuki 有 $5$ 種揀木棒嘅方法:$\{3,4,5\}$、$\{3,4,6\}$、$\{3,5,6\}$、$\{4,5,6\}$、$\{3,4,5,6\}$,每種方法都可以砌成非退化凸多邊形;好容易證明冇更大嘅合法子集。

  • $\{3,4,5,6,9\}$ 唔係合法子集,因為長度係 $3,4,9$ 嘅木棒砌唔成非退化三角形。

  • $\{3,5,6\}$ 唔係合法子集,因為有更大嘅合法子集。

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.