题目详情题解（0）讨论（0）提交记录（0）

AT_abc220_g.[ABC220G] Isosceles Trapezium

省选/NOI-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

在 xyxy 平面上有 NN 个点，每个点都有一个权值。
第 ii 个点的坐标为 (Xi,Yi)(X_i, Y_i)，权值为 CiC_i。

请从 NN 个点中选出 44 个点，使得它们作为顶点能够构成一个面积为正的等腰梯形。
在这种情况下，所选 44 个点的权值和的最大值是多少？

如果无法构成等腰梯形，请输出 −1-1。

等腰梯形需满足以下所有条件：

  • 是梯形；
  • 在两条平行边中，其中一条边的两个端点的角相等。

输入格式

输入以如下格式从标准输入给出。

NN
X1 Y1 C1X_1\ Y_1\ C_1
X2 Y2 C2X_2\ Y_2\ C_2
⋮\vdots
XN YN CNX_N\ Y_N\ C_N

输出格式

请输出答案。

输入输出样例

  • 输入#1

    5
0 3 10
3 3 10
-1 0 10
2 0 10000
4 0 10

    输出#1

    40

  • 输入#2

    6
0 1 1
1 4 20
2 7 300
5 6 4000
4 3 50000
3 0 600000

    输出#2

    650021

  • 输入#3

    7
-3 0 1
-2 0 1
-1 0 1
0 0 1
1 0 1
2 0 1
3 0 1

    输出#3

    -1

说明/提示

限制条件

  • 4≤N≤10004 \leq N \leq 1000
  • −109≤Xi,Yi≤109-10^9 \leq X_i, Y_i \leq 10^9
  • 1≤Ci≤1091 \leq C_i \leq 10^9
  • 若 i≠ji \neq j，则 (Xi,Yi)≠(Xj,Yj)(X_i, Y_i) \neq (X_j, Y_j)
  • 所有输入均为整数

样例解释 1


选择点 1,2,3,51,2,3,5 可以构成等腰梯形，点的权值和为 4040。除此之外，没有其他选法可以构成等腰梯形。

样例解释 2


请注意，正方形和长方形也属于等腰梯形。

样例解释 3

无法构成等腰梯形。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页