QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 512 MB Total points: 100 Hackable ✓

#17351. Would You Make a Convex?

Statistics

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, \dots, a_n$($1 \le a_i \le 10^9$)。

保证所有测试用例中 $n$ 的总和不超过 $5 \cdot 10^5$。

输出格式

对于每个测试用例,输出一行:

  • 如果不存在这样的子集,输出单个整数 0
  • 如果存在这样的子集,首先输出一个整数 $k$,表示你找到的子集的大小,随后输出 $k$ 个整数 $b_1, \dots, 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.