2020浙江省赛 H - Huge Clouds(线段树/差分求线段交并)

UCPRER 2020-10-21 10:15:00
原文地址:https://www.cnblogs.com/ucprer/p/13850858.html

<https://codeforces.com/gym/102770/problem/H&gt;

题意:

在二维平面上给定一些点一些线段,定义在x轴上一个点u,如果点u和任意一个给定点v的连线和所有给定线段都不相交(包括端点),则u不在阴影中。问x轴上阴影的长度(>1e9则输出-1)。

思路:

首先对每个点预处理出会被线段遮挡的范围。考虑一个点被一条线段遮挡,产生的阴影是一条线段或者一个射线,因为题目要求最后答案>1e9则输出-1,而且给定的点都是整点,因此可以将射线转为一个端点 为INF(1e12)的线段。一个点被遮挡的范围就是它被所有线段遮挡产生的线段的并。求出每个点遮挡范围之后,对所有点的遮挡范围取交集,交集中的长度就是答案。关键就是如何求线段并和线段集合的交。

解法1:

求线段并:将线段按左端点排序,从前往后遍历,依次将新的线段和已有的最右边的线段合并即可,保证每次合并后线段之间没有重复区间。

求线段集合的交:对所有线段集合中的所有线段左右端点进行离散化,建立线段树,对每条线段而言就是在线段树的对应区间上+1,最后询问线段树上哪些区间最大值=n,最小值=n。

#include &lt;bits/stdc++.h&gt;
#define rson rt&lt;&lt;1|1
#define lson rt&lt;&lt;1
#define mid ((l+r)&gt;&gt;1)
using namespace std;
const int maxn=505;
const double eps = 1e-6;
const double INF=1e18;
int sgn(double x) {
    if(fabs(x) &lt; eps)
        return 0;
    if(x &lt; 0)
        return -1;
    return 1;
}
struct Point {
    double x,y;
    Point() {}
    Point(double _x,double _y) {
        x = _x;
        y = _y;
    }
    Point operator -(const Point &amp;b)const {
        return Point(x - b.x,y - b.y);
    }
    Point operator +(const Point &amp;b)const {
        return Point(x + b.x,y +b.y);
    }
    double operator ^(const Point &amp;b)const {
        return x*b.y - y*b.x;
    }
    double operator *(const Point &amp;b)const {
        return x*b.x + y*b.y;
    }
};
double xmult(Point p0,Point p1,Point p2) { //p0p1 X p0p2
    return (p1-p0)^(p2-p0);
}
struct Line{
    Point s,t;
    Line(Point X=Point(),Point Y=Point()){
        s=X,t=Y;
    }
};
Point getIntersectPoint(Line a, Line b) {
    double a1 = a.s.y - a.t.y, b1 = a.t.x - a.s.x, c1 = a.s.x * a.t.y - a.t.x * a.s.y;
    double a2 = b.s.y - b.t.y, b2 = b.t.x - b.s.x, c2 = b.s.x * b.t.y - b.t.x * b.s.y;
    return Point((c1*b2-c2*b1)/(a2*b1-a1*b2), (a2*c1-a1*c2)/(a1*b2-a2*b1));
}
Point p[maxn];
Line l[maxn];
struct XD{
    double l,r;
}xd[maxn][maxn];
int cnt[maxn];
bool pequal(Point &amp;a,Point &amp;b){
    Point temp=a-b;
    if(sgn(temp.x)==0 &amp;&amp; sgn(temp.y)==0)
        return 1;
    else
        return 0;
}
XD getShadow(Point a,Line b){
    //特判a在b端点上
    if(pequal(a,b.s)||pequal(a,b.t)){
        return{-INF,INF};
    }
    Point pp[]={b.s,b.t};
    Line x={Point(0,0),Point(10000,0)};
    if(pp[0].y&gt;pp[1].y)swap(pp[0],pp[1]);
    //特判a在b上
    if(pp[0].y&lt;a.y &amp;&amp;  a.y&lt;pp[1].y){
        if(sgn((a-pp[0])^(pp[1]-a))==0){
            return {-INF,INF};
        }
    }
    if(a.y&gt;pp[1].y){
        Line l1={a,pp[0]};
        Line l2={a,pp[1]};
        double xx[2];
        xx[0]=getIntersectPoint(l1,x).x;
        xx[1]=getIntersectPoint(l2,x).x;
        if(xx[0]&gt;xx[1])swap(xx[0],xx[1]);
        return {xx[0],xx[1]};
    }
    else if(a.y&gt;pp[0].y){
        Line l2={a,pp[0]};
        double xx=getIntersectPoint(l2,x).x;
        if(xmult(pp[0],pp[1],a)&lt;0){//直线在点左边
            return {-INF,xx};
        }
        else{
            return {xx,INF};
        }
    }
    else{
        return {0,0};
    }
}
bool cmp(XD a,XD b){
    return a.l&lt;b.l;
}
double lisan[(maxn*maxn*2)];
int lisancnt=0;

//区间加,区间最大/最小
int Tmax[(maxn*maxn*2)&lt;&lt;2],Tmin[(maxn*maxn*2)&lt;&lt;2];
int lazy[(maxn*maxn*2)&lt;&lt;2];
void push_up(int rt,int l,int r){
    Tmax[rt]=max(Tmax[lson],Tmax[rson]);
    Tmin[rt]=min(Tmin[lson],Tmin[rson]);
}
void push_down(int rt,int l,int r){
    if(!lazy[rt])return;
    Tmax[lson]+=lazy[rt];Tmax[rson]+=lazy[rt];
    Tmin[lson]+=lazy[rt];Tmin[rson]+=lazy[rt];
    lazy[lson]+=lazy[rt];lazy[rson]+=lazy[rt];
    lazy[rt]=0;
}
void add(int rt,int l,int r,int ql,int qr,int value){
    if(l&gt;qr || r&lt;ql)return;
    if(ql&lt;=l &amp;&amp; r&lt;=qr){
        lazy[rt]+=value;
        Tmax[rt]+=value;
        Tmin[rt]+=value;
        return;
    }
    push_down(rt,l,r);
    if(r==l+1)return;//到叶子节点
    if(ql&lt;=mid-1)add(lson,l,mid,ql,qr,value);
    if(qr&gt;=mid+1)add(rson,mid,r,ql,qr,value);
    push_up(rt,l,r);
}
double query(int rt,int l,int r,int value){
    double ans=0;
    if(Tmax[rt]==value &amp;&amp; Tmin[rt]==value){
        ans+=lisan[r]-lisan[l];
        return ans;
    }
    push_down(rt,l,r);
    if(Tmax[lson]==value)ans+=query(lson,l,mid,value);
    if(Tmax[rson]==value)ans+=query(rson,mid,r,value);
    return ans;
}
void init(int n,int m){
    memset(Tmax,0,sizeof(int)*((n*m*2)*4+2));
    memset(Tmin,0,sizeof(int)*((n*m*2)*4+2));
    memset(lazy,0,sizeof(int)*((n*m*2)*4+2));
    lisancnt=0;
}
int main () {
    int T;
    scanf(&quot;%d&quot;,&amp;T);
    while(T--){
        int n,m;
        scanf(&quot;%d%d&quot;,&amp;n,&amp;m);
        init(n,m);
        for(int i=1;i&lt;=n;i++){
            scanf(&quot;%lf%lf&quot;,&amp;p[i].x,&amp;p[i].y);
        }
        for(int i=1;i&lt;=m;i++){
            scanf(&quot;%lf%lf%lf%lf&quot;,&amp;l[i].s.x,&amp;l[i].s.y,&amp;l[i].t.x,&amp;l[i].t.y);
        }
        for(int i=1;i&lt;=n;i++){
            for(int j=1;j&lt;=m;j++){
                xd[i][j]=getShadow(p[i],l[j]);
            }
            sort(xd[i]+1,xd[i]+1+m,cmp);
            cnt[i]=1;
            for(int j=2;j&lt;=m;j++){
                if(xd[i][cnt[i]].r&gt;xd[i][j].l){//有重复区域直接合并
                    xd[i][cnt[i]].r=max(xd[i][cnt[i]].r,xd[i][j].r);
                }
                else{
                    xd[i][++cnt[i]]=xd[i][j];
                }
            }
            for(int j=1;j&lt;=cnt[i];j++){
                lisan[++lisancnt]=xd[i][j].l;
                lisan[++lisancnt]=xd[i][j].r;
            }
        }
        sort(lisan+1,lisan+1+lisancnt);
        for(int i=1;i&lt;=n;i++){
            for(int j=1;j&lt;=cnt[i];j++){
                int left=lower_bound(lisan+1,lisan+1+lisancnt,xd[i][j].l)-lisan;
                int right=lower_bound(lisan+1,lisan+1+lisancnt,xd[i][j].r)-lisan;
                add(1,1,lisancnt,left,right,1);
            }
        }
        double ans=query(1,1,lisancnt,n);
        if(ans&gt;=1e9){
            puts(&quot;-1&quot;);
        }
        else
            printf(&quot;%.10f\n&quot;,ans);
    }
}

解法2:

求线段并:建立map<double,int> m1,对于所有线段在m1上进行差分,即m1[l]++,m1[r]--,最后遍历m1,前缀和>0开始至前缀和=0这样的区间就是最终覆盖范围中的一个线段。

求线段集合的交:建立map<double,int> m2,对于所有线段集合中所有线段进行差分,即m2[l]++,m2[r]--,之后遍历m2,前缀和=n开始至前缀和<n这样的区间就是一个阴影区间,直接对答案加上贡献即可。

#include &lt;bits/stdc++.h&gt;
#define rson rt&lt;&lt;1|1
#define lson rt&lt;&lt;1
#define mid ((l+r)&gt;&gt;1)
using namespace std;
const int maxn=505;
const double eps = 1e-6;
const double INF=1e18;
int sgn(double x) {
    if(fabs(x) &lt; eps)
        return 0;
    if(x &lt; 0)
        return -1;
    return 1;
}
struct Point {
    double x,y;
    Point() {}
    Point(double _x,double _y) {
        x = _x;
        y = _y;
    }
    Point operator -(const Point &amp;b)const {
        return Point(x - b.x,y - b.y);
    }
    Point operator +(const Point &amp;b)const {
        return Point(x + b.x,y +b.y);
    }
    double operator ^(const Point &amp;b)const {
        return x*b.y - y*b.x;
    }
    double operator *(const Point &amp;b)const {
        return x*b.x + y*b.y;
    }
};
double xmult(Point p0,Point p1,Point p2) { //p0p1 X p0p2
    return (p1-p0)^(p2-p0);
}
struct Line{
    Point s,t;
    Line(Point X=Point(),Point Y=Point()){
        s=X,t=Y;
    }
};
Point getIntersectPoint(Line a, Line b) {
    double a1 = a.s.y - a.t.y, b1 = a.t.x - a.s.x, c1 = a.s.x * a.t.y - a.t.x * a.s.y;
    double a2 = b.s.y - b.t.y, b2 = b.t.x - b.s.x, c2 = b.s.x * b.t.y - b.t.x * b.s.y;
    return Point((c1*b2-c2*b1)/(a2*b1-a1*b2), (a2*c1-a1*c2)/(a1*b2-a2*b1));
}
Point p[maxn];
Line l[maxn];
struct XD{
    double l,r;
};
bool pequal(Point &amp;a,Point &amp;b){
    Point temp=a-b;
    if(sgn(temp.x)==0 &amp;&amp; sgn(temp.y)==0)
        return 1;
    else
        return 0;
}
XD getShadow(Point a,Line b){
    //特判a在b端点上
    if(pequal(a,b.s)||pequal(a,b.t)){
        return{-INF,INF};
    }
    Point pp[]={b.s,b.t};
    Line x={Point(0,0),Point(10000,0)};
    if(pp[0].y&gt;pp[1].y)swap(pp[0],pp[1]);
    //特判a在b上
    if(pp[0].y&lt;a.y &amp;&amp;  a.y&lt;pp[1].y){
        if(sgn((a-pp[0])^(pp[1]-a))==0){
            return {-INF,INF};
        }
    }
    if(a.y&gt;pp[1].y){
        Line l1={a,pp[0]};
        Line l2={a,pp[1]};
        double xx[2];
        xx[0]=getIntersectPoint(l1,x).x;
        xx[1]=getIntersectPoint(l2,x).x;
        if(xx[0]&gt;xx[1])swap(xx[0],xx[1]);
        return {xx[0],xx[1]};
    }
    else if(a.y&gt;pp[0].y){
        Line l2={a,pp[0]};
        double xx=getIntersectPoint(l2,x).x;
        if(xmult(pp[0],pp[1],a)&lt;0){//直线在点左边
            return {-INF,xx};
        }
        else{
            return {xx,INF};
        }
    }
    else{
        return {0,0};
    }
}
bool cmp(XD a,XD b){
    return a.l&lt;b.l;
}
int main () {
    int T;
    scanf(&quot;%d&quot;,&amp;T);
    while(T--){
        int n,m;
        scanf(&quot;%d%d&quot;,&amp;n,&amp;m);
        for(int i=1;i&lt;=n;i++){
            scanf(&quot;%lf%lf&quot;,&amp;p[i].x,&amp;p[i].y);
        }
        for(int i=1;i&lt;=m;i++){
            scanf(&quot;%lf%lf%lf%lf&quot;,&amp;l[i].s.x,&amp;l[i].s.y,&amp;l[i].t.x,&amp;l[i].t.y);
        }
        map&lt;double,int&gt;m2;
        for(int i=1;i&lt;=n;i++){
            map&lt;double,int&gt;m1;
            for(int j=1;j&lt;=m;j++){
                XD temp=getShadow(p[i],l[j]);
                m1[temp.l]++;
                m1[temp.r]--;
            }
            int temp=0,flag=0;
            double pre=0;
            for(auto x:m1){
                temp+=x.second;
                if(temp&gt;0 &amp;&amp; !flag){
                    pre=x.first;
                    flag=1;
                }
                else if(temp==0 &amp;&amp; flag){
                    m2[pre]++;
                    m2[x.first]--;
                    flag=0;
                }
            }
        }
        int temp=0,flag=0;
        double pre=0,ans=0;
        for(auto x:m2){
            temp+=x.second;
            if(temp==n &amp;&amp; !flag){
                pre=x.first;
                flag=1;
            }
            else if(temp&lt;n &amp;&amp; flag){
                ans+=x.first-pre;
                flag=0;
            }
        }
        if(ans&gt;1e9)
            puts(&quot;-1&quot;);
        else
            printf(&quot;%.10f\n&quot;,ans);
    }
}

声明:该文章系转载,转载该文章的目的在于更广泛的传递信息,并不代表本网站赞同其观点,文章内容仅供参考。

本站是一个个人学习和交流平台,网站上部分文章为网站管理员和网友从相关媒体转载而来,并不用于任何商业目的,内容为作者个人观点, 并不代表本网站赞同其观点和对其真实性负责。

我们已经尽可能的对作者和来源进行了通告,但是可能由于能力有限或疏忽,导致作者和来源有误,亦可能您并不期望您的作品在我们的网站上发布。我们为这些问题向您致歉,如果您在我站上发现此类问题,请及时联系我们,我们将根据您的要求,立即更正或者删除有关内容。本站拥有对此声明的最终解释权。