#P4614. [Wf2016]Oil

    ID: 3290 传统题 1500ms 512MiB 尝试: 363 已通过: 56 难度: 7 上传者: 标签>难度分类提高+/省选-枚举与搜索暴力枚举计算几何扫描线离线与分治事件排序模拟与实现技巧同时事件分阶段处理数值计算与优化有理数精确运算CF2300鸣谢Yts1999上传lbn187提供译文

[Wf2016]Oil

[ICPC2016 WF] Oil

题目描述

在二维模型中,地表是 y=0y=0,深度沿 yy 的正方向。每个油藏是地表下的一条水平线段,储量等于线段长度。

从地表沿一条直线向地下钻井。该直线与油藏相交时,可以开采该油藏的全部储量。恰好穿过线段端点也算相交。求一口井最多能开采多少石油。

样例一的油藏分布和一条穿过三个油藏的井线

输入格式

第一行一个整数 nn,1≤n≤20001\le n\le2000,表示油藏数量。接下来 nn 行,每行三个整数 x0,x1,yx_0,x_1,y,给出油藏的两个端点 (x0,y)(x_0,y) 和 (x1,y)(x_1,y)。端点按任意顺序给出,可以重合。∣x0∣,∣x1∣≤106|x_0|,|x_1|\le10^6,1≤y≤1061\le y\le10^6。任意两个不同油藏没有公共点。

输出格式

输出一个整数,表示一口井能够开采的最大储量。

5
100 180 20
30 60 30
70 110 40
10 40 50
0 80 70
200
3
50 60 10
-42 -42 20
25 0 10
25