标签:扫描线

【算法】 扫描线求矩形面积并 —— by 蒟蒻XZY

1. 序言

求矩形面积并指的是给你n个矩形的顶点坐标(矩形的边必然平行于坐标轴),求它们所覆盖的总面积(重叠覆盖的面积只算一次覆盖)。
暴力枚举矩形的话如果n较大显然会超时。这时候我们就需要一种新算[......]

[继续阅读= ̄ω ̄=]

Read MoreComment

【题解】 Atlantis 扫描线 线段树 离散化 HDU – 1542

1. 题目

传送门= ̄ω ̄=
题目大意:给出n个矩形(矩形顶点左边可能为小数)1<=n<=100,求这些矩形覆盖的面积大小(多次覆盖同一个地方只算一次覆盖),即求这些矩形的面积并。含多组[......]

[继续阅读= ̄ω ̄=]

Read MoreComment

【题解】 扇形面积并 SHOI2013 扫描线 线段树 -boshi

扇形面积并

这道题比矩形面积并友好多了。

题意:给定n个同心扇形,放置在一个被半径2m等分的圆中(圆是假想的),求被扇形覆盖了k次以上的关于面积的代数式$\frac{\pi}{2m}\times[......]

[继续阅读= ̄ω ̄=]

Read MoreComment

【题解】【二维线段树】Atlantis(UVALive 2184)-boshi

题意:给定很多个(大概100个)矩形,的左上角右下角坐标(不一定为整数),要求它们的面积的并。

分析:这道题的数据非常水,只是test case可能会比较多。所以 O(n3) 爆力过不了。只能想想有[......]

[继续阅读= ̄ω ̄=]

Read MoreComment