[JOI Open 2017] 推土机 / Bulldozer

Luogu

IDLGP10630

Time2000ms

Memory512MB

DifficultyP6

2017JOI（日本）

**译自 [JOI Open 2017](https://contests.ioi-jp.org/open-2017/index.html) T2 「ブルドーザー / Bulldozer」** 平面上有 $N$ 个点，点 $i\:(1≤i≤N)$ 位于 $(X_i, Y_i)$，点 $i\:(1≤i≤N)$ 的权值为非零整数 $W_i$（可能为负数）。在平面上画两条平行线，所得的总价值为平行线之间（压线也算）所有点的权值之和。求总价值至多不超过多少。 ## Input 第一行包含一个整数 $N$。在接下来的 $N$ 行中，第 $i$ 行包含三个用空格分隔的整数 $X_i,Y_i,W_i$。 ## Output 一行，一个整数，表示最大总价值。 [samples] ## Note **样例解释 1** ![](https://cdn.luogu.com.cn/upload/image_hosting/rk2miemg.png) 选择点 $2, 3, 4, 5$。 **样例解释 2** 注意，点 $1,2,3$ 共线。点 $4,5,6$ 共线。 **样例解释 3** 这组样例中没有三点共线。选择的平行线一条过点 $1,2$，另一条过点 $3,4$。 #### 数据范围所有输入数据都满足以下条件。 $1≤N≤2000, |X_i|,|Y_i|≤10^9,1 ≤|W_i|≤10^9(1≤i≤N)$ 。$(X_i,Y_i)≠(X_j,Y_j)\:(1≤i<j≤N)$ 。 |子任务|分值|$N≤100$|无三点共线|设 $L$ 是在平面上通过两个不同点的一条线，$L'$ 是在平面上另一条通过两个不同点的线，那么 $L$ 和 $L'$ **不**相互平行|其他条件| |:---------:|:------------:|:-------------:|:---------------:|:-:|:------------:| |$1$ |$5$ |√ |× |×|所有点都在 $x$ 轴上| |$2$ |$20$ |√ |√ |√|无| |$3$ |$35$ |× |√ |√|无| |$4$ |$20$ |× |√ |×|无| |$5$ |$20$ |× |× |×|无|

Samples

Input #1

Output #1

Input #2

Output #2

Input #3

Output #3

Input #4

2
0 0 -1
1 0 -1

Output #4

API Response (JSON)

{
  "problem": {
    "name": "[JOI Open 2017] 推土机 / Bulldozer",
    "description": {
      "content": "**译自 [JOI Open 2017](https://contests.ioi-jp.org/open-2017/index.html) T2 「ブルドーザー / Bulldozer」** 平面上有 $N$ 个点，点 $i\\:(1≤i≤N)$ 位于 $(X_i, Y_i)$，点 $i\\:(1≤i≤N)$ 的权值为非零整数 $W_i$（可能为负数）。   在平面上画两条平行线，所得的总价值为平",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10630"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "**译自 [JOI Open 2017](https://contests.ioi-jp.org/open-2017/index.html) T2 「ブルドーザー / Bulldozer」**\n\n平面上有 $N$ 个点，点 $i\\:(1≤i≤N)$ 位于 $(X_i, Y_i)$，点 $i\\:(1≤i≤N)$ 的权值为非零整数 $W_i$（可能为负数）。  \n在平面上画两条平行线，所得的总价值为平...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments