闪了!!

自己的一点想法,不知道对不对

如果不对,欢迎各位神犇前来鄙视

那个,就是把路线分成若干段,每段中全都是一个方向

然后以起点(其它随便什么点也可以)为原点建立一个坐标系,路线中的每一段就是一条线段,算出线段两端的坐标并把横向和竖向的线段分别排序

然后一列一列地扫描,把当前列的所有线段插入一个线段树,然后查找最长的空白区域(就是两点间没有其它点的区域,可能不存在)并更新答案,做好了之后再把线段删掉

然后再一行行地扫描一遍

类似最大子段和,需要在线段树上维护sum,maxl,maxr,maxm四个域,还得考虑各种特殊情况,似乎挺麻烦

这样应该就差不多了,但是坐标可能很大,需要离散,更加麻烦

另外,数据中如果真的有250000条线段,这种做法可能会TLE

还有就是Pascal显然过不了,要用C++