P3635 [APIO2012] 苦无

洛谷
题目要求计算覆盖面积。
考虑如何计算两个苦无是否会相撞，又会在什么时候相撞。
如果两个方向分别向上下方向那么需要满足 \(x\) 坐标相等。
两个相遇时消耗的时间为两个的 \(y\) 坐标差值的一半（简单的相遇问题）。
左右方向同理可得。
然后考虑如果一个向下，一个向左，那么怎么判断是否会相遇。
我们先假设相撞的点为 \((x,y)\)，经过的时间为 \(t\)。
那么向北原本处于 \((x,y+t)\)，向东的原本处于 \((x-t,y)\)。
那么不难发现，我们需要保证这两个点的横坐标纵坐标差相等，并且方向要正确。
移项发现需要满足 \(y-x\) 的值相等时才有机会相撞。
其它的也用类似的方法推理即可。
那么我们把所有相撞方式分为 \(6\) 种，然后把有机会相撞的都给塞到一个 set 或者链表中。
按照横坐标或者纵坐标的值排序，显然相邻的两个更快相撞，并且如果两个无法相撞，那么两个可以看作两个需要反方向移动才能撞到，那么自然不用考虑越过这两个的点相撞。
判断能否相撞有直接枚举所有情况判断的笨方法，但实际上也可以改一下时间计算方法，如果计算出是负数或者方向相等则不会相撞，这样大概可以简化代码。
那么我们判断每个相邻的能否相撞，如果是，那么就加入一个小根堆中，每次把最小的取出来，进行修改即可。
注意多个撞到一起的情况也要考虑。
那么我们直接使用时间来计算，还需要关注小数点的存在。
那么我们就把所有时间先乘上二即可。
处理完后再除以二。
然后我们将其看作一个矩形，用求矩形面积并的方法即可求出最后答案。
点击查看代码[code]#include#define int long longusing namespace std;int H,W,n,fir[6],idd;struct P{        int x,y,d;}a[100005];map mp[6];struct Q{        int op,x,id;        bool friend operator>n;        for(int i=1;i>a.x>>a.y>>a.d;                if(a.d==0)add(i,0),add(i,2),add(i,3),dis=W-a.x