2012-A3-0011

从 Trac 迁移的文章

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

原文章内容如下：

题意是求，在平面上每次对若干个矩形区域依次进行染色和插除操作，然后给出一条折线段，求这个折线段在染色区域内的长度。

显然只要求出折线段上每一段线段的染色部分长度即可。

对于每条线段关于每个矩形求一个相交的区间。

这个区间可以表示成 [l,r],0<=l<=r<=1,表示占用区间的比例，然后就可以对区间依次进行染色和消色操作了。

这个可以用O(n^2^),也可以O(n log n),此题的用n^2^的也可以过.

麻烦的地方在于求出一条线段和一个矩形的公共相交部分。

对于平行坐标轴的矩形，可以用一种比较简单的方法求出，首先把矩形看成2组平行线段，每组线段中间部分对线段求交，这个只要把相应的x或y坐标带入即可求得，然后归一化至[l,r],0<=l<=r<=1

然后再对另一组求一个[l',r'],最后就再对[0,1],[l,r],[l',r']求交，即可求出线段和矩形的交。之后的操作就都比较方便了，不详述了。


{{{
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
typedef double real;
typedef pair<real,real> itv;
const real eps = 1e-8;
inline real dv(int r0,int dr,int r1){
    return (real)(r1-r0) / dr;
}
inline void andi(real & a ,real & b ,real x ,real y){
    if(x>y)swap(x,y);
    if(a<x)a=x;
    if(b>y)b=y;
}
vector<itv> ha;
inline void cmax(real&a,real b){if(a<b)a=b;}
inline void cmin(real&a,real b){if(a>b)a=b;}
int xl[1024],yl[1024],xr[1024],yr[1024],t[1024];
int main(){
    int x,y,x0,y0;
    for(int n,m;scanf("%d%d",&n,&m)==2;){
        for(int i=0;i<n;++i)
            scanf("%d%d%d%d%d",t+i,xl+i,yl+i,xr+i,yr+i);
        scanf("%d%d",&x0,&y0);
        real ans =0,l,r;
        for(int i=1;i<m;(++i),(x0+=x),(y0+=y)){
            scanf("%d%d",&x,&y);
            x-=x0;y-=y0;
            if(!(x||y))continue;
            ha.clear();
            for(int j=0;j<n;++j){
                l =0;r=1;
                if(x&&y){
                    andi(l,r,dv(y0,y,yl[j]),dv(y0,y,yr[j]));
                    andi(l,r,dv(x0,x,xl[j]),dv(x0,x,xr[j]));
                    if(l>r)l=r=-1;
                }else
                if(x==0){
                    if(x0>=xl[j] && x0<=xr[j])
                        andi(l,r,dv(y0,y,yl[j]),dv(y0,y,yr[j]));
                    else l = r =-1;
                }else
                if(y==0){
                    if(y0>=yl[j]&& y0<=yr[j])
                        andi(l,r,dv(x0,x,xl[j]),dv(x0,x,xr[j]));
                    else l = r =-1;
                }
                if(r-l<eps)continue;
                if(t[j]==1){
                    ha.push_back(make_pair(l,r));
                    sort(ha.begin(),ha.end());
                    size_t i,j;
                    for(i=0,j=1;i<ha.size();){
                        for(;j<ha.size() &&
                             ha[j].first <= ha[i].second;++j){
                                cmax(ha[i].second ,ha[j].second);
                        }
                        ++i;
                        if(j<ha.size()){
                            ha[i]=ha[j];
                        }else break;
                    }
                    ha.resize(i);
                }else{
                    for(size_t i=0;i<ha.size();++i){
                        if(ha[i].first<l && ha[i].second>r){
                            ha.push_back(make_pair(r,ha[i].second));
                            ha[i].second =l;
                            break;
                        }
                        if(ha[i].first>=l && ha[i].second <=r)
                            ha[i].first = 99;
                        if(ha[i].first<l && ha[i].second>l)
                            ha[i].second=l;
                        if(ha[i].first<r && ha[i].second>r)
                            ha[i].first=r;
                    }
                    sort(ha.begin(),ha.end());
                    while(ha.size()&&ha.rbegin()->first>1)ha.pop_back();
                }
            }
            real len =0;
            for(size_t i=0;i<ha.size();++i)
                len+= ha[i].second-ha[i].first;
            //printf("%lf\n",len*hypot(x,y));
            ans += len*hypot(x,y);
        }
        printf("%.2lf\n",ans);
    }
    return 0;
}
}}}

题意是求，在平面上每次对若干个矩形区域依次进行染色和插除操作，然后给出一条折线段，求这个折线段在染色区域内的长度。

显然只要求出折线段上每一段线段的染色部分长度即可。

对于每条线段关于每个矩形求一个相交的区间。

这个区间可以表示成 [l,r],0<=l<=r<=1,表示占用区间的比例，然后就可以对区间依次进行染色和消色操作了。

这个可以用O(n²),也可以O(n log n),此题的用n²的也可以过.

麻烦的地方在于求出一条线段和一个矩形的公共相交部分。

对于平行坐标轴的矩形，可以用一种比较简单的方法求出，首先把矩形看成2组平行线段，每组线段中间部分对线段求交，这个只要把相应的x或y坐标带入即可求得，然后归一化至[l,r],0<=l<=r<=1

然后再对另一组求一个[l',r'],最后就再对[0,1],[l,r],[l',r']求交，即可求出线段和矩形的交。之后的操作就都比较方便了，不详述了。

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
typedef double real;
typedef pair<real,real> itv;
const real eps = 1e-8;
inline real dv(int r0,int dr,int r1){
    return (real)(r1-r0) / dr;
}
inline void andi(real & a ,real & b ,real x ,real y){
    if(x>y)swap(x,y);
    if(a<x)a=x;
    if(b>y)b=y;
}
vector<itv> ha;
inline void cmax(real&a,real b){if(a<b)a=b;}
inline void cmin(real&a,real b){if(a>b)a=b;}
int xl[1024],yl[1024],xr[1024],yr[1024],t[1024];
int main(){
    int x,y,x0,y0;
    for(int n,m;scanf("%d%d",&n,&m)==2;){
        for(int i=0;i<n;++i)
            scanf("%d%d%d%d%d",t+i,xl+i,yl+i,xr+i,yr+i);
        scanf("%d%d",&x0,&y0);
        real ans =0,l,r;
        for(int i=1;i<m;(++i),(x0+=x),(y0+=y)){
            scanf("%d%d",&x,&y);
            x-=x0;y-=y0;
            if(!(x||y))continue;
            ha.clear();
            for(int j=0;j<n;++j){
                l =0;r=1;
                if(x&&y){
                    andi(l,r,dv(y0,y,yl[j]),dv(y0,y,yr[j]));
                    andi(l,r,dv(x0,x,xl[j]),dv(x0,x,xr[j]));
                    if(l>r)l=r=-1;
                }else
                if(x==0){
                    if(x0>=xl[j] && x0<=xr[j])
                        andi(l,r,dv(y0,y,yl[j]),dv(y0,y,yr[j]));
                    else l = r =-1;
                }else
                if(y==0){
                    if(y0>=yl[j]&& y0<=yr[j])
                        andi(l,r,dv(x0,x,xl[j]),dv(x0,x,xr[j]));
                    else l = r =-1;
                }
                if(r-l<eps)continue;
                if(t[j]==1){
                    ha.push_back(make_pair(l,r));
                    sort(ha.begin(),ha.end());
                    size_t i,j;
                    for(i=0,j=1;i<ha.size();){
                        for(;j<ha.size() &&
                             ha[j].first <= ha[i].second;++j){
                                cmax(ha[i].second ,ha[j].second);
                        }
                        ++i;
                        if(j<ha.size()){
                            ha[i]=ha[j];
                        }else break;
                    }
                    ha.resize(i);
                }else{
                    for(size_t i=0;i<ha.size();++i){
                        if(ha[i].first<l && ha[i].second>r){
                            ha.push_back(make_pair(r,ha[i].second));
                            ha[i].second =l;
                            break;
                        }
                        if(ha[i].first>=l && ha[i].second <=r)
                            ha[i].first = 99;
                        if(ha[i].first<l && ha[i].second>l)
                            ha[i].second=l;
                        if(ha[i].first<r && ha[i].second>r)
                            ha[i].first=r;
                    }
                    sort(ha.begin(),ha.end());
                    while(ha.size()&&ha.rbegin()->first>1)ha.pop_back();
                }
            }
            real len =0;
            for(size_t i=0;i<ha.size();++i)
                len+= ha[i].second-ha[i].first;
            //printf("%lf\n",len*hypot(x,y));
            ans += len*hypot(x,y);
        }
        printf("%.2lf\n",ans);
    }
    return 0;
}