/ Vijos / 题库 / 强墙 /

题解

87 条题解

  • 3
    @ 2017-05-07 12:47:15

    /*
    嗯一道计算几何+最短路
    黑书上计算几何有这道题目
    其实题目不难的
    唯一的难度就是判断两点能否直接到达
    即两点连线上是否有别的墙挡住
    这个据说是可以用叉积很快的
    但是如果用相似三角形比例
    也是可以写出来的
    然后我们对于每堵墙两个洞即四个点
    我们可以判断能否在一条直线上中间无障碍物
    如果可以就是他们的欧几里得距离
    如果不可以就设为INF
    建立邻接矩阵
    然后随便跑个最短路就好了
    还是FLoyd最方便最快捷
    Orz主要还是最好写2333333333
    然后判断是否能连线
    我这种弱弱真的懒得写啊
    就随便复制了个叉积的然后改了一下用进来了
    千万别学我Orz
    嗯就这样水过去吧
    */

    #include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include <cstring>
    using namespace std;
    
    const int MAXN=100;
    const double INF=999.0;
    struct node
    {
        double x,y;
    }p[MAXN];
    int n,K;
    double d[MAXN][MAXN];
    
    double inline ojld(int i,int j)
    {
        return sqrt((p[i].x-p[j].x)*(p[i].x-p[j].x)
                   +(p[i].y-p[j].y)*(p[i].y-p[j].y));
    }
    
    double det(double x1,double y1,double x2,double y2)//行列式
    {
    return x1*y2-x2*y1;
    }
    double cross(node p0,node p1,node p2)//叉积
    {
    double ans = det(p1.x-p0.x,p1.y-p0.y,p2.x-p0.x,p2.y-p0.y);
    return ans;
    }
    bool check(int a,int b)//判断能否连通
    {
    if(p[a].x == p[b].x) return false;
    for(int i = a+1;i < b;i++)
       {
       if(p[i].x == p[a].x || p[i].x == p[b].x) continue;
       node temp;
       if(i%4==1)
         {
         temp.x = p[i].x,temp.y = 10;
         if(cross(p[a],p[b],temp)*cross(p[a],p[b],p[i]) < 0 && cross(temp,p[i],p[a])*cross(temp,p[i],p[b]) < 0)
           return false;
         }
       if(i%4==0)
         {
         temp.x = p[i].x,temp.y = 0;
         if(cross(p[a],p[b],temp)*cross(p[a],p[b],p[i]) < 0 && cross(temp,p[i],p[a])*cross(temp,p[i],p[b]) < 0)
           return false;
         }
       if(i%4==2)
         {
         temp.x = p[i+1].x,temp.y = p[i+1].y;
         if(cross(p[a],p[b],temp)*cross(p[a],p[b],p[i]) < 0 && cross(temp,p[i],p[a])*cross(temp,p[i],p[b]) < 0)
           return false;
         }
       }
    return true;
    }
    
    void init()
    {
        double x;
        cin>>n;
        K=4*n+1;
        for(int i=0;i<n;i++)
        {
            cin>>x;
            p[i*4+1].x=p[i*4+2].x=p[i*4+3].x=p[i*4+4].x=x;
            cin>>p[i*4+4].y>>p[i*4+3].y>>p[i*4+2].y>>p[i*4+1].y;
        }
        p[0].x=0,p[0].y=5;
        p[K].x=10,p[K].y=5;
        for(int i=0;i<=K;i++)
            for(int j=0;j<=K;j++)
                d[i][j]=INF;
    }
    
    void getd()
    {
        for(int i=0;i<=K;i++)
            for(int j=i+1;j<=K;j++)
                if(check(i,j))
                    d[i][j]=ojld(i,j);
    }
    
    void Floyd()
    {
        for(int k=0;k<=K;k++)
            for(int i=0;i<=K;i++)
                for(int j=0;j<=K;j++)
                    d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
        printf("%.2lf\n",d[0][K]);
    }
    
    int main()
    {
        init();
        getd();
        Floyd();
        return 0;
    }
    
  • 1
    @ 2017-10-22 20:00:06

    区间DP的思路很容易就可以写出来
    需要注意的是细节比较多,小数点和等号也比较诡异
    判断能否联通直接斜率硬算就可以

    #include<iostream>
    #include<cstring>
    #include<cmath>
    #include<cstdio>
    using namespace std;
    
    struct wall{
        double x;
        double a[5];
    }q[22];
    
    double minn[22][5];
    int pan[22][22][5][5];
    
    int main()
    {
        int n,i,j,u,k,v;
        double xie,now;
        memset(pan,0,sizeof(pan));
        cin>>n;
        for(i=1;i<=n;i++)
        {
            cin>>q[i].x>>q[i].a[1]>>q[i].a[2]>>q[i].a[3]>>q[i].a[4];
        }
        q[0].x=0;
        q[0].a[1]=q[0].a[2]=q[0].a[3]=q[0].a[4]=5;
        q[n+1].x=10;
        q[n+1].a[1]=q[n+1].a[2]=q[n+1].a[3]=q[n+1].a[4]=5;
        for(i=1;i<=n+1;i++)
        {
            for(k=0;k<i;k++)
            {
                for(j=1;j<=4;j++)
                 for(u=1;u<=4;u++)
                  {
                   if(k==i-1)
                  {
                    pan[i][k][j][u]=1;
                    continue;
                  }
                   xie=(q[i].a[j]-q[k].a[u])/(q[i].x-q[k].x);
                   for(v=k+1;v<i;v++)
                   {
                    now=q[k].a[u]+xie*(q[v].x-q[k].x);
                    if(now>=q[v].a[1]&&now<=q[v].a[2])
                     continue;
                    if(now>=q[v].a[3]&&now<=q[v].a[4])
                     continue;
                     break;
                   }
                 if(v>=i)
                  pan[i][k][j][u]=1;
            }
        }
        
    }
        for(i=1;i<=n+1;i++)
        {
            for(k=0;k<i;k++)
            {
                for(j=1;j<=4;j++)
                {
                    for(u=1;u<=4;u++) 
                     if(pan[i][k][j][u])
                      if(minn[i][j]!=0)
                     minn[i][j]=min(minn[i][j],minn[k][u]+sqrt((q[i].x-q[k].x)*(q[i].x-q[k].x)+(q[i].a[j]-q[k].a[u])*(q[i].a[j]-q[k].a[u])));
                      else
                     minn[i][j]=minn[k][u]+sqrt((q[i].x-q[k].x)*(q[i].x-q[k].x)+(q[i].a[j]-q[k].a[u])*(q[i].a[j]-q[k].a[u]));       
                
                }
                
            }
        }
        printf("%.2lf",minn[n+1][2]);
        return 0;
    } 
    
  • 0
    @ 2017-07-21 14:47:12

    思路:每个线段端点都来一发,判相交(叉积),连边(欧几里德距离),最短路。

    这是改了4次 ,4次的代码啊,终于写出来了,不容易啊!!!

    #include<algorithm>
    #include<iostream>
    #include<cstring>
    #include<cstdio>
    #include<vector>
    #include<queue>
    #include<cmath>
    #define inf (118)
    #define eps (1e-8)
    using namespace std;
    struct POINT {
        double x,y;
        POINT operator + (POINT tm) {
            return (POINT) {
                x+tm.x,y+tm.y
            };
        }
        POINT operator - (POINT tm) {
            return (POINT) {
                x-tm.x,y-tm.y
            };
        }
        double operator * (POINT tm) {
            return x*tm.x-y*tm.y;
        }
        double operator ^ (POINT tm) {
            return x*tm.y-y*tm.x;
        }
    };
    struct EDGE {
        int u,v;
        double dis;
    };
    int n;
    int pcnt,pst,ped;
    double lis[150];
    POINT pset[150];
    int lnset[30][5];
    vector<EDGE> eset[150];
    int sign (double tm) {
        if (fabs(tm)<eps) return 0;
        else return tm>0?1:-1;
    }
    
    double distant (POINT tma,POINT tmb) {
    
        return sqrt((tma.x-tmb.x)*(tma.x-tmb.x)+(tma.y-tmb.y)*(tma.y-tmb.y));
    
    }
    bool csjudge (POINT tma,POINT tmb,POINT tmc,POINT tmd) {
    
        if (sign(((tmc-tma)^(tmd-tma))*((tmc-tmb)^(tmd-tmb)))>=0) return 0;
        if (sign(((tma-tmc)^(tmb-tmc))*((tma-tmd)^(tmb-tmd)))>=0) return 0;
        return 1;
    
    }
    int pmake (double x,double y) {
    
        pset[++pcnt]=(POINT) {
            x,y
        };
        return pcnt;
    
    }
    void emake (int tma,int tmb) {
    
        POINT tmpa=pset[tma],tmpb=pset[tmb];
        double dis=distant(tmpa,tmpb);
        eset[tma].push_back((EDGE) {tma,tmb,dis});
        return;
    
    }
    void spfa (int p) {
    
        queue<int> qu;
        bool vis[150];
        qu.push(p);
        memset(lis,inf,sizeof(lis)),lis[p]=0;
        memset(vis,0,sizeof(vis)),vis[p]=1;
        while(!qu.empty()) {
            int now=qu.front();
            qu.pop();
            for(int i=0; i<eset[now].size(); i++) {
                int nxt=eset[now][i].v;
                double dis=eset[now][i].dis;
                if (lis[now]+dis<lis[nxt]) {
                    if (!vis[nxt]) {
                        qu.push(nxt);
                        vis[nxt]=1;
                        lis[nxt]=lis[now]+dis;
                    }
                    lis[nxt]=lis[now]+dis;
                }
            }
            vis[now]=0;
        }
        return;
    
    }
    bool judge (int tma,int tmb) {
    
        POINT tmpa=pset[tma],tmpb=pset[tmb];
        for(int i=1; i<=n; i++) {
            POINT pa=pset[lnset[i][1]],pb=pset[lnset[i][2]],
            pc=pset[lnset[i][3]],pd=pset[lnset[i][4]];
            POINT lowp=(POINT) {pa.x,0},highp=(POINT) {pa.x,10};
            if (tmpa.x>=pa.x||tmpb.x<=pa.x) continue;
            if (csjudge(tmpa,tmpb,lowp,pa)) return 0;
            if (csjudge(tmpa,tmpb,pb,pc)) return 0;
            if (csjudge(tmpa,tmpb,pd,highp)) return 0;
        }
        return 1;
    
    }
    void clear () {
    
        pcnt=pst=ped=0;
        memset(pset,0,sizeof(pset));
        memset(lnset,0,sizeof(lnset));
        memset(eset,0,sizeof(eset));
    
    }
    int main () {
    
        scanf("%d",&n);
        for(int i=1; i<=4; i++) lnset[0][i]=pmake(0,5),lnset[n+1][i]=pmake(10,5);
        pst=lnset[0][1],ped=lnset[n+1][1];
        double x,y;
        for(int i=1; i<=n; i++) {
            scanf("%lf",&x);
            for(int j=1; j<=4; j++) {
                scanf("%lf",&y);
                lnset[i][j]=pmake(x,y);
            }
        }
        for(int i=1; i<=n+1; i++)
            for(int j=0; j<i; j++)
                for(int o=1; o<=4; o++)
                    for(int g=1; g<=4; g++)
                        if (judge(lnset[j][g],lnset[i][o]))
                            emake(lnset[j][g],lnset[i][o]),emake(lnset[i][o],lnset[j][g]);
        spfa(pst);
        printf("%.2f\n",lis[ped]);
        return 0;
    
    }
    

  • 0
    @ 2016-12-21 12:13:46

    第一眼以为是贪心...

  • 0
    @ 2016-08-25 22:25:37

    dp或者是dij思路都很容易,但是判断线段相交真的是坑。
    之前用相似三角形和定比分点一直20分,怎么改都是20分
    后来用叉积判断线段相交,AC了
    所以不太清楚下面那些用除法的是怎么过的...

  • 0
    @ 2016-05-03 16:18:59

    典型的计算几何。构造一个图,把所有互相能看见的点对连接成边,生成一个邻接矩阵,随后最短路即可。
    如何判断点对之间能否相互看见呢?假定它们相连成边 e,只需遍历所有墙,看看是否与边 e 相交即可。

    var
    a:array[0..30,0..4]of real;
    i,j,jj,k,m,n:Longint;
    p:real;
    dis:array[0..30,0..4]of real;
    function len(i,j,x,y:Longint):real;
    begin
    exit(sqrt(sqr(a[i,j]-a[x,y])+sqr(a[i,0]-a[x,0])));
    end;
    function can(x,y,x1,y1:Longint):boolean;{看x边上的y点与x1边上的y1点能否看到}
    var
    i,j:longint;
    yy:real;
    begin
    for i:=x+1 to x1-1 do
    begin
    if a[x1,y1]=a[x,y] then yy:=a[x,y]
    else
    yy:=(a[i,0]-a[x,0])*(a[x1,y1]-a[x,y])/(a[x1,0]-a[x,0])+a[x,y];
    if not ( ((yy>=a[i,1])and(yy<=a[i,2]))or ((yy>=a[i,3])and(yy<=a[i,4])))
    then exit(false);
    end;
    exit(true);
    end;
    begin
    read(n);
    a[0,0]:=0;
    a[n+1,0]:=10;
    for i:=1 to 4 do
    begin
    a[0,i]:=5;
    a[n+1,i]:=5;
    end;
    for i:=1 to n do
    for j:=0 to 4 do
    read(a[i,j]);

    for I:=1 to n+1 do
    begin
    for j:=1 to 4 do

    for jj:=0 to i-1 do
    for k:=1 to 4 do
    if can(jj,k,i,j) then
    begin
    p:=dis[jj,k]+len(jj,k,i,j);
    if (dis[i,j]=0)or(dis[i,j]>p) then
    dis[i,j]:=p;
    end;

    end;
    writeln(dis[n+1,1]:0:2);
    end.

  • 0
    @ 2016-02-17 21:24:16

    总体思路 能互相看到的两点之间的边加入图 然后是最短路问题
    Floyd dij全秒杀 不要忘了两头能直接相连
    虽说是水题,但技术还是不行啊。。交了好几次。。全细节错误。。

    program dij;
    var
        w:array[0..100,0..100] of double;
        xy:array[0..25,0..5] of double;
        i,j,k,n,p:integer;
    function line(x1,y1,x2,y2:double):boolean;
    var 
      i:integer;
        b,k,t:double;
    begin
        if x1=x2 then exit(false);
        k:=(y1-y2)/(x1-x2);
        b:=y1-k*x1;
        for i:=1 to n do
          begin
                t:=k*xy[i,0]+b;
                if ((xy[i,0]>x1) and (xy[i,0]<x2)) or ((xy[i,0]<x1) and (xy[i,0]>x2)) then
                    if (t<xy[i,1]) or (t>xy[i,4]) or ((t>xy[i,2]) and (t<xy[i,3]))then
                      exit(false);
            end;
        exit(true);
    end;
    function dis(x1,y1,x2,y2:double):double;
    begin
      exit(sqrt(sqr(x1-x2)+sqr(y1-y2)));
    end;
    begin
      read(n);
        for i:=1 to n do
            for j:=0 to 4 do read(xy[i,j]);
        for i:=1 to 4*n+2 do
          for j:=1 to 4*n+2 do
              if i<>j then w[i,j]:=99
                    else w[i,j]:=0;
        xy[0,0]:=0;xy[0,1]:=5;xy[n+1,0]:=10;xy[n+1,1]:=5;
        for i:=0 to n+1 do
          if (i=0) or (i=n+1) then
                begin
                for j:=1 to n do
                    for k:=1 to 4 do
                        if line(xy[i,0],xy[i,1],xy[j,0],xy[j,k]) then
                        begin
                            if i=0 then 
                                begin
                                    w[1,(j-1)*4+1+k]:=dis(xy[i,0],xy[i,1],xy[j,0],xy[j,k]);
                                    w[(j-1)*4+1+k,1]:=dis(xy[i,0],xy[i,1],xy[j,0],xy[j,k]);
                                end
                            else 
                                begin
                                    w[4*n+2,(j-1)*4+1+k]:=dis(xy[i,0],xy[i,1],xy[j,0],xy[j,k]);
                                    w[(j-1)*4+1+k,4*n+2]:=dis(xy[i,0],xy[i,1],xy[j,0],xy[j,k]);
                            end
                        end
                end
            else
                for p:=1 to 4 do
                  for j:=1 to n do
                        for k:=1 to 4 do
                          if line(xy[i,0],xy[i,p],xy[j,0],xy[j,k]) then
                                begin
                                    w[(i-1)*4+1+p,(j-1)*4+1+k]:=dis(xy[i,0],xy[i,p],xy[j,0],xy[j,k]);
                                    w[(j-1)*4+1+k,(i-1)*4+1+p]:=dis(xy[i,0],xy[i,p],xy[j,0],xy[j,k]);
                                end;
        if line(xy[0,0],xy[0,1],xy[n+1,0],xy[n+1,1]) then w[1,4*n+2]:=dis(xy[0,0],xy[0,1],xy[n+1,0],xy[n+1,1]);
        for k:=1 to 4*n+2 do
            for i:=1 to 4*n+2 do
                for j:=1 to 4*n+2 do
                    if w[i,j]>w[i,k]+w[k,j] then w[i,j]:=w[i,k]+w[k,j];
        writeln(w[1,4*n+2]:0:2);
    end.
    
  • 0
    @ 2015-04-12 16:42:42

    典型的计算几何。只需构造一个图,把所有互相能看见的点对连接成边,生成一个邻接矩阵,随后最短路即可。有人说用 floyd 或 SPFA,好像没必要吧,毕竟是点对点且无负权,Dijkstra 秒杀。
    如何判断点对之间能否相互看见呢?假定它们相连成边 e,只需遍历所有墙,看看是否与边 e 相交即可。由于这道题的墙都是竖直的,所以还算好处理,直接解析式算得了,没必要用向量叉积那种方法。
    最后上代码

    #include <stdio.h>
    #include <math.h>
    #include <limits.h>

    #define SQR(a) ((a)*(a))
    #define X 0
    #define Y 1
    #define Y1 1
    #define Y2 2

    double vertices[100][2];
    double edges[80][3];
    double map[100][100];

    double value[100];
    int used[100];

    void addEdge(int index,double x,double y1,double y2){
    edges[index][X]=x;
    edges[index][Y1]=y1;
    edges[index][Y2]=y2;
    }

    int intersect(int indexP1,int indexP2,int indexEdge){
    double x1,x2,y1,y2,y3,y4;
    double k,b,x;

    x1=vertices[indexP1][X],x2=vertices[indexP2][X];
    y1=vertices[indexP1][Y],y2=vertices[indexP2][Y];
    x=edges[indexEdge][X];
    y3=edges[indexEdge][Y1],y4=edges[indexEdge][Y2];

    k=(y2-y1)/(x2-x1);
    b=y1-k*x1;
    if(k*x+b>y3 && k*x+b<y4)
    return 1;
    else
    return 0;
    }

    int main(){
    int num,numVertex,numEdge;
    int i,k,n,m,flag,source;
    double x,min;

    /*read data*/
    scanf("%d",&num);
    numVertex=num*4+2;
    numEdge=num*3;
    vertices[0][X]=0;
    vertices[0][Y]=5;
    for(i=n=1,m=0;i<=num;i++){
    scanf("%lf",&x);
    for(k=0;k<4;k++){
    vertices[n][X]=x;
    scanf("%lf",&vertices[n][Y]);
    n++;
    }
    addEdge(m,x,0,vertices[n-4][Y]);
    addEdge(m+1,x,vertices[n-3][Y],vertices[n-2][Y]);
    addEdge(m+2,x,vertices[n-1][Y],10);
    m+=3;
    }
    vertices[numVertex-1][X]=10;
    vertices[numVertex-1][Y]=5;

    /*create a map*/
    for(i=0;i<numVertex;i++){
    for(k=0;k<numVertex;k++)
    map[i][k]=0;
    }
    for(i=0;i<numVertex;i++){
    for(k=i+1;k<numVertex;k++){
    //try to connect them together
    if(vertices[i][X]==vertices[k][X])
    continue;
    flag=1;
    for(n=0;n<numEdge;n++){
    if(vertices[i][X]>=edges[n][X])
    continue;
    if(vertices[k][X]<=edges[n][X])
    break;
    if(intersect(i,k,n)){
    flag=0;
    break;
    }
    }
    if(flag){
    map[i][k]=map[k][i]=sqrt(
    SQR(vertices[i][X]-vertices[k][X]) + SQR(vertices[i][Y]-vertices[k][Y])
    );
    }
    }
    }

    /*shortest path*/
    for(i=0;i<numVertex;i++){
    value[i]=LONG_MAX;
    used[i]=0;
    }
    value[0]=0;
    for(i=0;i<numVertex;i++){
    min=LONG_MAX;
    for(k=0;k<numVertex;k++){
    if(!used[k] && min>value[k]){
    min=value[k];
    source=k;
    }
    }
    used[source]=1;
    for(k=0;k<numVertex;k++){
    if(map[source][k]>0 && value[k]>value[source]+map[source][k])
    value[k]=value[source]+map[source][k];
    }
    }

    /*output solution*/
    printf("%.2lf\n",value[numVertex-1]);

    return 0;
    }

  • 0
    @ 2015-01-26 10:55:53

    构图最短路.
    每个墙的端点设一个点.对于点对(i,j),(i在j左边),如果i,j中间没有墙那么连一条i到j的有向边.
    同样的方法处理起点和终点,然后SPFA.
    由于生成的图总是DAG,也可以记忆化搜索.

  • 0
    @ 2014-07-14 20:29:14

    这是什么叼情况?
    测试数据 #0: WrongAnswer, time = 15 ms, mem = 804 KiB, score = 0
    测试数据 #1: Accepted, time = 15 ms, mem = 800 KiB, score = 10
    测试数据 #2: Accepted, time = 0 ms, mem = 808 KiB, score = 10
    测试数据 #3: Accepted, time = 0 ms, mem = 804 KiB, score = 10
    测试数据 #4: Accepted, time = 31 ms, mem = 804 KiB, score = 10
    测试数据 #5: Accepted, time = 15 ms, mem = 804 KiB, score = 10
    WrongAnswer, time = 76 ms, mem = 808 KiB, score = 50

  • 0
    @ 2014-04-02 18:43:34

    为什么过不了!!!!!各大神!!!!!
    readln(n);
    for i:=1 to n do readln(l[i],a[1,i],b[1,i],a[2,i],b[2,i]);
    inc(n);
    a[1,0]:=5; b[1,0]:=5; a[2,0]:=5; b[2,0]:=5; l[0]:=0;
    a[1,n]:=5; b[1,n]:=5; a[2,n]:=5; b[2,n]:=5; l[n]:=10;
    for i:=0 to n do l[i]:=l[i]*100;
    //------------------------------------
    for i:=n-1 downto 0 do begin
    g:=f; fillchar(f,sizeof(f),$7f);
    for d1:=1 to 2 do
    for j:=trunc(a[d1,i]*100) to trunc(b[d1,i]*100) do
    for d2:=1 to 2 do
    for k:=trunc(a[d2,i+1]*100) to trunc(b[d2,i+1]*100) do
    f[j]:=min(f[j],g[k]+dis(l[i],j,l,k));
    end;

  • 0
    @ 2014-04-02 18:43:05

    readln(n);
    for i:=1 to n do readln(l[i],a[1,i],b[1,i],a[2,i],b[2,i]);
    inc(n);
    a[1,0]:=5; b[1,0]:=5; a[2,0]:=5; b[2,0]:=5; l[0]:=0;
    a[1,n]:=5; b[1,n]:=5; a[2,n]:=5; b[2,n]:=5; l[n]:=10;
    for i:=0 to n do l[i]:=l[i]*100;
    //------------------------------------
    for i:=n-1 downto 0 do begin
    g:=f; fillchar(f,sizeof(f),$7f);
    for d1:=1 to 2 do
    for j:=trunc(a[d1,i]*100) to trunc(b[d1,i]*100) do
    for d2:=1 to 2 do
    for k:=trunc(a[d2,i+1]*100) to trunc(b[d2,i+1]*100) do
    f[j]:=min(f[j],g[k]+dis(l[i],j,l,k));
    end;

  • 0
    @ 2014-02-02 21:31:20

    为何使用spfa倒数第二个点死活过不去。。

  • 0
    @ 2013-02-16 10:11:17
    • @ 2014-10-31 14:53:22

      nmd,你不要在这个网站上捣乱好不好?

    • @ 2015-08-12 18:47:27

      你脑洞小苹果了???

    • @ 2016-09-04 21:47:15

      有意思么?

  • 0
    @ 2012-07-17 16:10:14

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

    发一个丑陋的DP

    var

    n,i,j,k:longint;

    x,a1,b1,a2,b2:array[1..30] of double;

    f:array[1..20,1..4] of double;

    ans:double;

    function dis(x1,y1,x2,y2:double):double;

    begin

    exit(sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)));

    end;

    function min(a,b:double):double;

    begin

    if a>b then exit(b) else exit(a);

    end;

    function pan(i,j:longint;x1,y1,x2,y2:double):boolean;

    var

    p:longint;

    k,b:double;

    begin

    k:=(y2-y1)/(x2-x1);

    b:=y1-k*x1;

    for p:=i+1 to j-1 do

    if not (((k*x[p]+b=a1[p])) or ((k*x[p]+b=a2[p]))) then

    exit(false);

    exit(true);

    end;

    function make(p:longint;y:double):double;

    var

    i:longint;

    pa:boolean;

    k,ans:double;

    begin

    k:=(y-5)/x[p];

    pa:=true;

    for i:=1 to p-1 do

    if not (((k*x[i]+5=a1[i])) or ((k*x[i]+5=a2[i]))) then

    begin

    pa:=false;

    break;

    end;

    if pa then exit(dis(0,5,x[p],y));

    ans:=maxlongint;

    for i:=1 to p-1 do

    begin

    if pan(i,p,x[i],a1[i],x[p],y) then

    ans:=min(ans,f+dis(x[i],a1[i],x[p],y));

    if pan(i,p,x[i],b1[i],x[p],y) then

    ans:=min(ans,f+dis(x[i],b1[i],x[p],y));

    if pan(i,p,x[i],a2[i],x[p],y) then

    ans:=min(ans,f+dis(x[i],a2[i],x[p],y));

    if pan(i,p,x[i],b2[i],x[p],y) then

    ans:=min(ans,f+dis(x[i],b2[i],x[p],y));

    end;

    exit(ans);

    end;

    begin

    readln(n);

    for i:=1 to n do

    readln(x[i],a1[i],b1[i],a2[i],b2[i]);

    f[1,1]:=dis(0,5,x[1],a1[1]);

    f[1,2]:=dis(0,5,x[1],b1[1]);

    f[1,3]:=dis(0,5,x[1],a2[1]);

    f[1,4]:=dis(0,5,x[1],b2[1]);

    for i:=2 to n do

    begin

    f:=make(i,a1[i]);

    f:=make(i,b1[i]);

    f:=make(i,a2[i]);

    f:=make(i,b2[i]);

    end;

    x[n+1]:=10;

    writeln(make(n+1,5):0:2);

    end.

  • 0
    @ 2010-07-16 07:25:45

    n2DP?

    float x[22];

    float y[22][5];

    int N;

    float f[22][5]={0};

    #include

    int ok(int a,int b,int c,int d)

    {

    int i;

    float s;

    for(i=a+1;i=y[i][1]&&s=y[i][3]&&s

  • 0
    @ 2010-07-05 12:58:29

    silva胡说八道。

  • 0
    @ 2009-11-14 11:32:13

    FLOYD。。。。数据小的话编程很简单。。。

    判断的时候忘记判断X坐标了。。。WA了三次。。

    还有这题很多细节要注意。。。比如什么时候等号能取

  • 0
    @ 2009-10-28 09:53:36

    说是计算几何,实际上是dp。用标号法计算每个障碍物的两端点到重点的最短距离,最后得到起点到终点的最短距离。其中状态变量是每个点到终点的最短距离,每堵墙是一个阶段。

  • 0
    @ 2009-10-24 20:23:18

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

    茶几+spfa

信息

ID
1013
难度
7
分类
计算几何 点击显示
标签
(无)
递交数
2086
已通过
469
通过率
22%
被复制
1
上传者