CF #327 DIV2 D、E

两题都不难。

对于D题，可以使用相对移动，把吹aircraft移动变成相反方向的待援点的移动。假设此时时间为t，把aircraft的速度设为Vmax，看待援点在飞船最大速度飞行t秒的范围内，注意风向变化的时间点即可。其实很明显的二分。。

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 using namespace std;

 int x1,y1,x2,y2;

 double v,t;

 int fx,fy,sx,sy;

 double dis(double x,double y){

     return x*x+y*y;

 }

 bool ok(double st){

     if(st<=t){

         if(dis(x2-fx*st-x1,y2-fy*st-y1)-v*st*v*st>1e-) return false;

         else return true;

     }

     else{

         st-=t;

         if(dis(x2-fx*t-sx*st-x1,y2-fy*t-sy*st-y1)-v*v*(st+t)*(st+t)>1e-) return false;

         return true;

     }

 }

 int main(){

     while(scanf("%d%d%d%d",&x1,&y1,&x2,&y2)!=EOF){

         scanf("%lf%lf",&v,&t);

         scanf("%d%d%d%d",&fx,&fy,&sx,&sy);

         double l=,r=1e9;

         double ans=;

         while(r-l>1e-){

             double m=(r+l)/;

             if(ok(m)){

                 ans=m;

                 r=m;

             }

             else{

                 l=m;

             }

         }

         printf("%.8lf\n",ans);

     }

     return ;

 }

对于E题，我觉得我是傻B了。可以求出每个国家到其他国家的最近距离，当然了，此时使用BFS，求出每个点到从本国的边缘点出发的最近距离。

首先假设交接点在某个国家，这样求三次都取最近距离。

再假设交接点在空白的点上，取某点到三个国家最近的距离和。

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #include <queue>

 using namespace std;

 char str[][];

 int n,m;

 int dis[][][];

 struct Node{

     int x,y;

     Node(){}

     Node(int xx,int yy){

         x=xx,y=yy;

     }

 };

 int dir[][]={

     {,},

     {,},

     {-,},

     {,-}

 };

 int p[];

 bool ok(int x,int y){

     if(x<||x>n||y<||y>m) return false;

     return true;

 }

 void slove(int ind){

     queue<Node>que;

     for(int i=;i<=n;i++){

         for(int j=;j<=m;j++){

             if(str[i][j]==''+ind)

                 que.push(Node(i,j)),dis[ind][i][j]=,p[ind]=;

         }

     }

     Node tmp,nxt;

     while(!que.empty()){

         tmp=que.front();

         que.pop();

         for(int k=;k<;k++){

             nxt.x=tmp.x+dir[k][];

             nxt.y=tmp.y+dir[k][];

             if(!ok(nxt.x,nxt.y)) continue;

             if(dis[ind][nxt.x][nxt.y]!=-) continue;

             if(str[nxt.x][nxt.y]=='#') continue;

             dis[ind][nxt.x][nxt.y]=dis[ind][tmp.x][tmp.y]+;

             if(str[nxt.x][nxt.y]>=''&&str[nxt.x][nxt.y]<=''){

                 if(str[nxt.x][nxt.y]==''&&p[]==-) p[]=dis[ind][nxt.x][nxt.y];

                 if(str[nxt.x][nxt.y]==''&&p[]==-) p[]=dis[ind][nxt.x][nxt.y];

                 if(str[nxt.x][nxt.y]==''&&p[]==-) p[]=dis[ind][nxt.x][nxt.y];

             }

             que.push(Node(nxt.x,nxt.y));

         }

     }

 }

 int main(){

     while(scanf("%d%d",&n,&m)!=EOF){

         for(int i=;i<=n;i++){

             scanf("%s",str[i]+);

         }

         int ans=-;

         memset(dis[],-,sizeof(dis[]));

         memset(p,-,sizeof(p));

         slove();

         if(p[]!=-&&p[]!=-&&p[]!=-) ans=ans==-?p[]+p[]+p[]-:min(ans,p[]+p[]+p[]-);

         memset(dis[],-,sizeof(dis[]));

         memset(p,-,sizeof(p));

         slove();

         if(p[]!=-&&p[]!=-&&p[]!=-) ans=ans==-?p[]+p[]+p[]-:min(ans,p[]+p[]+p[]-);

         memset(dis[],-,sizeof(dis[]));

         memset(p,-,sizeof(p));

         slove();

         if(p[]!=-&&p[]!=-&&p[]!=-) ans=ans==-?p[]+p[]+p[]-:min(ans,p[]+p[]+p[]-);

         for(int i=;i<=n;i++){

             for(int j=;j<=m;j++){

                 if(dis[][i][j]==-) continue;

                 if(dis[][i][j]==-) continue;

                 if(dis[][i][j]==-) continue;

                 ans=ans==-?dis[][i][j]+dis[][i][j]+dis[][i][j]-:min(ans,dis[][i][j]+dis[][i][j]+dis[][i][j]-);

             }

         }

         printf("%d\n",ans);

     }

     return ;

 }

巴特西

CF #327 DIV2 D、E

最新文章

热门文章