老年蒟蒻关于半平面交模板的一个疑问

P4196 [CQOI2006] 凸多边形 /【模板】半平面交

新加入的边和队首的边围成的面积更小
by this_red_is_gone @ 2020-01-09 09:58:26


![](https://i.loli.net/2020/01/09/ANKs4rEIotyBe7Q.png ) 假设标号就是加入队列的顺序,当3加入的时候1和2的交点在红色处,这个时候不管先判断1就会弹1,先判断2就会弹2,但是1和3围成的面积更小,所以先弹后加入的
by this_red_is_gone @ 2020-01-09 10:01:32


@[red](/user/135950) 这么说不更应该是后者吗?
by ATHOSD @ 2020-01-09 10:02:58


![](https://i.loli.net/2020/01/09/lF6inDqVK8Im9fG.png ) 忘加箭头了qwq
by this_red_is_gone @ 2020-01-09 10:03:26


@[Athos_Dybala](/user/199346) 默认保留左半部分的话应该保留1弹出2的吧
by this_red_is_gone @ 2020-01-09 10:04:01


@[red](/user/135950) 懂了!谢谢!!
by yxsplay @ 2020-01-09 10:04:54


@[Athos_Dybala](/user/199346) 2是后加入的应该在队尾鸭
by this_red_is_gone @ 2020-01-09 10:05:03


@[red](/user/135950) 哦哦哦谢谢
by ATHOSD @ 2020-01-09 10:12:00


Orz
by jiqimao @ 2020-02-19 16:57:11


Orz
by zzy2333 @ 2020-03-27 18:11:39


|