首页 > 代码库 > BZOJ 2433 智能车比赛（计算几何+最短路）

BZOJ 2433 智能车比赛（计算几何+最短路）

2024-07-08 23:59:44   213人阅读

题目链接：http://61.187.179.132/JudgeOnline/problem.php?id=2433

题意:若干个矩形排成一排（同一个x之上最多有一个矩形），矩形i和i+1相邻。给定两点S和T，两点均在矩形内。求S到T的最短路径。只能在矩形内部走。

思路：首先，S到T若有转弯，必定是在矩形 的顶点处转弯。因此，只要建立任意两可达顶点（包含S和T）之间距离求最短路即可。若暴力枚举任意两点再判是否可达复杂度O(n^3)。优化。枚举起点 a，从左向右扫遍矩形，利用叉积维护关于该点a的上下界，在该范围之内的点均可达。

 

struct point{    int x,y;    point(){}    point(int _x,int _y)    {        x=_x;        y=_y;    }    void get()    {        RD(x,y);    }    point operator-(point a)    {        return point(x-a.x,y-a.y);    }    i64 operator*(point a)    {        return (i64)x*a.y-(i64)y*a.x;    }    double len()    {        return sqrt(1.0*x*x+1.0*y*y);    }};struct node{    point a,b,c,d;    void get()    {        int x1,y1,x2,y2;        RD(x1,y1); RD(x2,y2);        a=point(x1,y1);        b=point(x1,y2);        c=point(x2,y1);        d=point(x2,y2);    }    int contain(point p)    {        return a.x<=p.x&&p.x<=c.x&&a.y<=p.y&&p.y<=b.y;    }};double f[N],v,ans;node a[N];point S,T;int n;double dis(point a,point b){    a=a-b;    return a.len();}i64 cross(point a,point b,point c){    return (b-a)*(c-a);}int isCross(point a,point b,point c,point d){    if(b.x<a.x) return 0;    return cross(a,c,b)<=0&&cross(a,d,b)>=0;}void update(point S,int now,double p){    if(p>=dinf) return;    point up=point(S.x,S.y+1);    point down=point(S.x,S.y-1);    point l,r;    int i;    for(i=now;i<n;i++)    {        if(isCross(S,a[i].a,up,down)) f[i*4]=min(f[i*4],p+dis(S,a[i].a));        if(isCross(S,a[i].b,up,down)) f[i*4+1]=min(f[i*4+1],p+dis(S,a[i].b));        if(isCross(S,a[i].c,up,down)) f[i*4+2]=min(f[i*4+2],p+dis(S,a[i].c));        if(isCross(S,a[i].d,up,down)) f[i*4+3]=min(f[i*4+3],p+dis(S,a[i].d));        if(a[i].contain(T)&&isCross(S,T,up,down)) ans=min(ans,p+dis(S,T));        if(i+1<n)        {            l=point(a[i].c.x,max(a[i].c.y,a[i+1].a.y));            r=point(a[i].d.x,min(a[i].d.y,a[i+1].b.y));            if(a[i].c.x==S.x)            {                if(l.y>S.y||S.y>r.y)                {                    f[(i+1)*4]=min(f[(i+1)*4],p+dis(S,a[i+1].a));                    f[(i+1)*4+1]=min(f[(i+1)*4+1],p+dis(S,a[i+1].b));                    return;                }            }            else            {                if(cross(S,down,l)>0) down=l;                if(cross(S,up,r)<0) up=r;                if(cross(S,up,down)>0) return;            }        }    }}int main(){    RD(n);    int i;    FOR0(i,n) a[i].get();    S.get(); T.get();    RD(v);    if(S.x>T.x) swap(S,T);    FOR0(i,4*n) f[i]=dinf;    ans=dinf;    FOR0(i,n)    {        if(a[i].contain(S)) update(S,i,0);        update(a[i].a,i,f[i*4]);        update(a[i].b,i,f[i*4+1]);        update(a[i].c,i,f[i*4+2]);        update(a[i].d,i,f[i*4+3]);    }    PR(ans/v);}

 

 

 


联系
我们