team2012-E1-mysol-0011

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
/* 解题报告 //

给出 n <= 1000 个矩形的绘制或擦除操作，再给出 m <= 100 段的折线段
求线段上被绘制部分的长度

这题我在比赛时一直考虑如何做矩形切割，得到一个个互不相交的小矩形
然后再对折线段的覆盖面积进行计算

实际上，这么做是很困难的，因为最坏情况下矩形有 O(n ^ 2) 个
乘上线段的数量再乘上 case 数后很容易超时
且 O(n ^ 2 log n) 的矩形切割本身也很慢了，而且相当不好写
更何况边界的处理是非常难的一件事

如果换一种想法，直接对每条线段处理在其之上的所有矩形
就可以将矩形添加与删除，变成线段的添加与删除

于是依次处理，对于每条线段 i，求出它与每个矩形 j 的相交区间 Cij
将每个区间化成两个事件点 (pos_left, j_start) 和 (pos_right, j_end)
放到 vector 中，等到相交的部分处理完后，对整个 vector 排一下序

然后对 vector 遍历，在处理每个事件之前，
先计算当前区间（上个事件点的位置到这个事件点的位置）是否被覆盖
可以用一个 set<int> 去维护覆盖当前区间的所有矩形的编号
计算时，取出编号最大的矩形，如果是绘制操作，则 ans += 当前区间长度
计算完当前区间后，再处理事件：
1. 如果类型是 j_start，则将 j 插入到 set<int> 内
2. 如果类型是 j_end，则从 set<int> 中删除 j

关于计算矩形与线段相交具体是怎么做的，zYc 学长那边写得比较详细
大家可以去看看他的解题报告

// By 猛犸也钻地 @ 2012.07.21 */
}}}

{{{
#include <cstdio>
#include <vector>
#include <set>
#include <cmath>
#include <algorithm>
using namespace std;

typedef pair<double,double> PDD;
typedef pair<double,int> PDI;

int tp[1000],ax[1000],ay[1000],bx[1000],by[1000];

inline double sqr(double x){
    return x*x;
}

PDD cross(int i, int sx, int sy, int tx, int ty){
    if(sx>tx) swap(sx,tx),swap(sy,ty);
    double ux=max(sx,ax[i])-sx,vx=min(tx,bx[i])-sx;
    double lx=abs(tx-sx),ly=abs(ty-sy),uy=0,vy=0;
    if(sy<ty) uy=max(sy,ay[i])-sy,vy=min(ty,by[i])-sy;
    if(sy>ty) uy=sy-min(sy,by[i]),vy=sy-max(ty,ay[i]);
    if(sx==tx && sx>=ax[i] && sx<=bx[i]) return PDD(uy/ly,vy/ly);
    if(sy==ty && sy>=ay[i] && sy<=by[i]) return PDD(ux/lx,vx/lx);
    if(sx!=tx && sy!=ty) return PDD(max(ux/lx,uy/ly),min(vx/lx,vy/ly));
    return PDD(-1,-2);
}

int main(){
    int n,m;
    while(scanf("%d%d",&n,&m)==2){
        for(int i=0;i<n;i++)
            scanf("%d%d%d%d%d",tp+i,ax+i,ay+i,bx+i,by+i);
        int sx,sy,tx,ty;
        scanf("%d%d",&sx,&sy);
        double ans=0;
        for(int i=1;i<m;i++){
            scanf("%d%d",&tx,&ty);
            vector<PDI> u;
            for(int j=0;j<n;j++){
                PDD c=cross(j,sx,sy,tx,ty);
                if(c.first>=c.second) continue;
                u.push_back(PDI(c.first,~j));
                u.push_back(PDI(c.second,j));
            }
            sort(u.begin(),u.end());
            set<int> o;
            double p=0,len=sqrt(sqr(tx-sx)+sqr(ty-sy));
            for(size_t j=0;j<u.size();p=u[j++].first){
                if(o.size() && tp[*o.rbegin()]) ans+=(u[j].first-p)*len;
                if(u[j].second<0) o.insert(~u[j].second); else o.erase(u[j].second);
            }
            sx=tx,sy=ty;
        }
        printf("%.2f\n",ans);
    }
}
}}}

/* 解题报告 //
给出 n <= 1000 个矩形的绘制或擦除操作，再给出 m <= 100 段的折线段
求线段上被绘制部分的长度
这题我在比赛时一直考虑如何做矩形切割，得到一个个互不相交的小矩形
然后再对折线段的覆盖面积进行计算
实际上，这么做是很困难的，因为最坏情况下矩形有 O(n ^ 2) 个
乘上线段的数量再乘上 case 数后很容易超时
且 O(n ^ 2 log n) 的矩形切割本身也很慢了，而且相当不好写
更何况边界的处理是非常难的一件事
如果换一种想法，直接对每条线段处理在其之上的所有矩形
就可以将矩形添加与删除，变成线段的添加与删除
于是依次处理，对于每条线段 i，求出它与每个矩形 j 的相交区间 Cij
将每个区间化成两个事件点 (pos_left, j_start) 和 (pos_right, j_end)
放到 vector 中，等到相交的部分处理完后，对整个 vector 排一下序
然后对 vector 遍历，在处理每个事件之前，
先计算当前区间（上个事件点的位置到这个事件点的位置）是否被覆盖
可以用一个 set<int> 去维护覆盖当前区间的所有矩形的编号
计算时，取出编号最大的矩形，如果是绘制操作，则 ans += 当前区间长度
计算完当前区间后，再处理事件：
1. 如果类型是 j_start，则将 j 插入到 set<int> 内
2. 如果类型是 j_end，则从 set<int> 中删除 j
关于计算矩形与线段相交具体是怎么做的，zYc 学长那边写得比较详细
大家可以去看看他的解题报告
// By 猛犸也钻地 @ 2012.07.21 */

#include <cstdio>
#include <vector>
#include <set>
#include <cmath>
#include <algorithm>
using namespace std;
typedef pair<double,double> PDD;
typedef pair<double,int> PDI;
int tp[1000],ax[1000],ay[1000],bx[1000],by[1000];
inline double sqr(double x){
    return x*x;
}
PDD cross(int i, int sx, int sy, int tx, int ty){
    if(sx>tx) swap(sx,tx),swap(sy,ty);
    double ux=max(sx,ax[i])-sx,vx=min(tx,bx[i])-sx;
    double lx=abs(tx-sx),ly=abs(ty-sy),uy=0,vy=0;
    if(sy<ty) uy=max(sy,ay[i])-sy,vy=min(ty,by[i])-sy;
    if(sy>ty) uy=sy-min(sy,by[i]),vy=sy-max(ty,ay[i]);
    if(sx==tx && sx>=ax[i] && sx<=bx[i]) return PDD(uy/ly,vy/ly);
    if(sy==ty && sy>=ay[i] && sy<=by[i]) return PDD(ux/lx,vx/lx);
    if(sx!=tx && sy!=ty) return PDD(max(ux/lx,uy/ly),min(vx/lx,vy/ly));
    return PDD(-1,-2);
}
int main(){
    int n,m;
    while(scanf("%d%d",&n,&m)==2){
        for(int i=0;i<n;i++)
            scanf("%d%d%d%d%d",tp+i,ax+i,ay+i,bx+i,by+i);
        int sx,sy,tx,ty;
        scanf("%d%d",&sx,&sy);
        double ans=0;
        for(int i=1;i<m;i++){
            scanf("%d%d",&tx,&ty);
            vector<PDI> u;
            for(int j=0;j<n;j++){
                PDD c=cross(j,sx,sy,tx,ty);
                if(c.first>=c.second) continue;
                u.push_back(PDI(c.first,~j));
                u.push_back(PDI(c.second,j));
            }
            sort(u.begin(),u.end());
            set<int> o;
            double p=0,len=sqrt(sqr(tx-sx)+sqr(ty-sy));
            for(size_t j=0;j<u.size();p=u[j++].first){
                if(o.size() && tp[*o.rbegin()]) ans+=(u[j].first-p)*len;
                if(u[j].second<0) o.insert(~u[j].second); else o.erase(u[j].second);
            }
            sx=tx,sy=ty;
        }
        printf("%.2f\n",ans);
    }
}