Line Segments Trace II

题目描述

有 n 个线段，其端点具有整数坐标。每个 x 坐标在 0 到 m 之间。每条线段的斜率是一个整数。 对于每个 x 坐标 0,1,$\dots$,m，求在任一线段上的最大点。如果某个点没有线段，则最大值为 -1。

输入格式

第一行有两个整数 n 和 m：线段的数量和最大的 x 坐标。 接下来的 n 行描述线段。每行有四个整数 x_1, y_1, x_2 和 y_2：存在一条连接点 (x_1,y_1) 和 (x_2,y_2) 的线段。

输出格式

输出 m+1 个整数：x=0,1,$\dots$,m 的最大点。

4 5
1 1 3 3
1 2 4 2
2 4 5 7
2 8 5 2

-1 2 8 6 6 7

提示

$1 \le n, m \le 10^5$ $0 \le x_1 < x_2 \le m$ $0 \le y_1,y_2 \le 10^9$

标签: CSES3428|几何

来源

CSES3428|几何