5444. Line Segments Trace II
时间限制：1000 MS 内存限制：256 MB
题目描述
## 题目描述 There are nnn line segments whose endpoints have integer coordinates. Each x-coordinate is between 000 and mmm. The slope of each segment is an integer. For each x-coordinate 0,1,\dots,m0,1,\dots,m0,1,\dots,m, find the maximum point in any line segment. If there is no segment at some point, the maximum is -1-1-1. ## 输入格式 The first line has two integers nnn and mmm: the number of line segments and the maximum x-coordinate. The next nnn lines describe the line segments. Each line has four integers x1x_1x1, y1y_1y1, x2x_2x2 and y2y_2y2: there is a line segment between points (x1,y1)(x_1,y_1)(x1,y1) and (x2,y2)(x_2,y_2)(x2,y2). ## 输出格式 Print m+1m+1m+1 integers: the maximum points for x=0,1,\dots,mx=0,1,\dots,mx=0,1,\dots,m. ## 数据范围 - 1\len,m\le1051 \le n, m \le 10^51\len,m\le105 - 0\lex1<x2\lem0 \le x_1 < x_2 \le m0\lex1<x2\lem - 0\ley1,y2\le1090 \le y_1,y_2 \le 10^90\ley1,y2\le109 ## 样例 ## 输入 ```in1 4 5 1 1 3 3 1 2 4 2 2 4 5 7 2 8 5 2 ``` ## 输出 ```out1 -1 2 8 6 6 7 ```