#3674. 道路网络(road)

道路网络(road)

题目描述

为追求城市的发展, A 城决定建设新的道路网络,这项规划计划建设n n 条道路。然而,每条道路的建设过程都面临着额外的挑战,因此为了保证项目的正常完工,需要准备充足的资金。

在道路的建设中,每当施工中的道路与已经建成的道路交汇时,必须搭建桥梁防止影响修建好的道路正常运行。而这个额外的建设环节,将产生额外的开支,需要注意的是,由于道路情况不同,因此每条道 路所需要建设的桥梁都有其独特的建设花费,vi v_i 代表了在与已建成道路交汇时所需投入的资金。

我们将需要建设的区域视为一个大小无限的平面坐标系。这里的 nn 条道路可以看作n n条不重合的直线 (这些直线有可能平行),每条直线都经过特定的点(xi,yi)(x_i, y_i),并具有一定的斜率ki k_i 。市政府需要制定预算,确保在最坏的情况下也能够完成新区道路建设。现在需要你提前计算出最坏的情况所需要的资金, 以便于市政府提前准备好充足的资金完成该项目的建设。

输入格式

第一行一个整数n n 代表道路的数量。

接下来 nn 行每行四个整数xi,yi,ki,vi x_i, y_i,k_i, v_i

对于第ii 条道路,xi,yi x_i, y_i 代表道路经过的点的坐标,ki k_i 代表道路的斜率, viv_i 代表建桥产生费用。

输出格式

输出一行一个整数代表答案。

样例

3
1 2 5 8
1 3 6 4
2 2 5 3
12
3
0 0 5 3
0 0 10 4
0 0 15 5
14

数据范围

  • 对于 10%的数据保证:1n101k1000001v1000001≤n≤10, 1≤k≤100000, 1≤v≤100000
  • 对于 40%的数据保证:1n10001k1000001v1000001≤n≤1000, 1≤k≤100000, 1≤v≤100000
  • 对于 60%的数据保证:1n1000001k1000001v1000001≤n≤100000, 1≤k≤100000, 1≤v≤100000
  • 对于 100%的数据保证:$1≤n≤100000, -100000≤k≤100000, 1≤v≤100000, -100000≤x,y≤100000$

来源

BCSP-X 2024 初中组 T2