Universal Cup Judging System

Universal Cup

実行時間制限: 1 s メモリ制限: 512 MB 満点: 100 ハック可能 ✓
統計

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.