/ Vijos / 题库 / 强墙 /

题解

88 条题解

  • 0
    @ 2009-04-10 23:15:50

    我记得代码不长啊,怎么到这里显得这么长??

    #include

    #include

    using namespace std;

    double f[30][5],a[30],b[30][5];

    int n;

    bool check(int x1,int y1,int x2,int y2)

    {

    for (int i=x1+1;ib[i][2]&&yy=0) return f[x][y];

    double s=10000000.23;

    if (check(x,y,n+1,0)) return hypot(a[n+1]-a[x],abs(b[n+1][0]-b[x][y]));

    for (int i=x+1;ib[i][1]>>b[i][2]>>b[i][3]>>b[i][4];

    printf("%.2f\n",search(0,0));

    return 0;

    }

    直接搜索……当然加了记忆化。本身就是dp,最开始时按搜索想的,就这么写了……

  • 0
    @ 2009-04-09 13:22:40

    发现我的代码写的又丑又长。。。

    #include

    #include

    using namespace std;

    const int MaxN = 100;

    struct Point

    {

    double x, y;

    } P[MaxN];

    struct Line

    {

    double x, a, b;

    } L[MaxN];

    double G[MaxN][MaxN];

    int N;

    bool Used[MaxN];

    double Ans[MaxN];

    double Dis(int a, int b)

    {

    return sqrt((P[a].x - P.x)*(P[a].x - P.x)+(P[a].y - P.y)*(P[a].y - P.y));

    }

    double max(double a, double b)

    {

    if (a > b) return a;

    else return b;

    }

    double min(double a, double b)

    {

    if (a > b) return b;

    else return a;

    }

    double Multi(Point pt1, Point pt2, Point pt0)

    {//向量的X乘,不是点乘

    //pt0视为原点

    //返回结果大于0pt1在PT2的在顺时针方向

    // < 0在逆时针方向

    // == 0两向量共线

    double x1 = pt1.x - pt0.x;

    double y1 = pt1.y - pt0.y;

    double x2 = pt2.x - pt0.x;

    double y2 = pt2.y - pt0.y;

    return x1 * y2 - x2*y1;

    }

    bool Chk(Line T, int a, int b)

    {

    Point p1, p2, q1, q2;

    p1.x = T.x, p1.y = T.a;

    p2.x = T.x, p2.y = T.b;

    q1 = P[a];

    q2 = P;

    if (!(max(p1.x, p2.x) >= min(q1.x, q2.x) && max(q1.x, q2.x) >= min(p1.x, p2.x) &&

    max(p1.y, p2.y) >= min(q1.y, q2.y) && max(q1.y, q2.y) >= min(p1.y, p2.y)))

    return 0;

    double t1 = Multi(q1, p2, p1);

    double t2 = Multi(q2, p2, p1);

    double t = t1*t2;

    if (t > 0) return 0;

    t1 = Multi(p1, q2, q1);

    t2 = Multi(p2, q2, q1);

    t = t1*t2;

    if (t > 0) return 0;

    return 1;

    }

    bool Chk(int a, int b)

    {

    if (a != 0)

    {

    if ((a - 1) / 4 + 1 == (b - 1) / 4) return 1;

    if ((a - 1) / 4 == (b - 1) / 4) return 0;

    bool Flag = 0;

    for (int i = (a - 1) / 4 + 1; i < (b - 1) / 4; i++)

    if (!Chk(L[i * 2 + 1], a, b) && !Chk(L[i * 2 + 2], a, b))//判断a、b的是否和一段空的线段存在交点

    {

    Flag = 1;

    break;

    }

    if (!Flag) return 1;

    }

    else

    {

    if ((b - 1) / 4 == 0) return 1;

    bool Flag = 0;

    for (int i = 0; i < (b - 1) / 4; i++)

    if (!Chk(L[i * 2 + 1], a, b) && !Chk(L[i * 2 + 2], a, b))//判断a、b的是否和一段空的线段存在交点

    {

    Flag = 1;

    break;

    }

    if (!Flag) return 1;

    }

    return 0;

    }

    int main()

    {

    scanf("%d", &N);

    for (int i = 0; i < N; i++)

    {

    double x, a1, a2, b1, b2;

    scanf("%lf%lf%lf%lf%lf", &x, &a1, &b1, &a2, &b2);

    P[i * 4 + 1].x = x, P[i * 4 + 1].y = a1;

    P[i * 4 + 2].x = x, P[i * 4 + 2].y = b1;

    P[i * 4 + 3].x = x, P[i * 4 + 3].y = a2;

    P[i * 4 + 4].x = x, P[i * 4 + 4].y = b2;

    L[i * 2 + 1].x = x, L[i * 2 + 1].a = a1, L[i * 2 + 1].b = b1;

    L[i * 2 + 2].x = x, L[i * 2 + 2].a = a2, L[i * 2 + 2].b = b2;

    }

    P[0].x = 0, P[0].y = 5;

    P[N * 4 + 1].x = 10, P[N * 4 + 1].y = 5;

    for (int i = 0; i

  • 0
    @ 2009-02-21 11:41:02

    自己DP写得太烂了,所以还是用最短路吧……

  • 0
    @ 2009-02-13 15:35:29

    黑书叉积例题,是我VJ上第三道用到叉积的题目

  • 0
    @ 2009-02-06 08:30:23

    [color=red+blue+black]

    楼下的写的真烁

    明显是胡说

  • 0
    @ 2009-02-05 13:47:58

    数据 弱到不行 ~~~~~~~加两面墙枚举每点与前面的所有点的可行路径O(4*(n+2))DP随便做就行

  • 0
    @ 2009-02-01 18:07:21

    ___|__ &&&&_) )

    \/,---|< &&&&&&\ \

    ( )c~c~~@~@ )- - &&\ \

    C >/ < |&/

    _O/ - 哇塞 _`*-'_/ /

    ,- >o

  • 0
    @ 2009-01-30 11:22:22

    我用我的算法

    老师刚教的:2点之间,线段最短

    秒杀

    (当然不能穿墙了。。)

  • 0
    @ 2009-01-23 10:28:06

    =。=||一次AC。。我的方法比较简单啊。。1.读入数据,把每个口的两个点用一个结构记录,每个点都记下来struct Node{ double x,y;}B[100];然后还要加上起点和终点。。把墙当作一条直线,struct Line{ double x,y1,y2;}C[100];2.然后就预处理,计算每个口上的点之间的距离,这里就要判断,这两个点之间的连线是否与某块墙有交点。。。3.然后就用最短路来求就对了。。。。

    #include#includeusing namespace std;const long N=30;const double Max=100000000.0;double g[100][100];long n,m=0,Lnum=0;struct Wall{ double x,a1,b1,a2,b2;}A[N];struct Node{ double x,y;}B[100];struct Line{ double x,y1,y2;}C[100];void Input(){ freopen("p1013.in","r",stdin); scanf("%ld",&n); ++m;B[m].x=0;B[m].y=5; ++m;B[m].x=10;B[m].y=5; for(long i=1;i

  • 0
    @ 2009-01-06 21:07:38

    原来可以按最短路做呀...

  • 0
    @ 2008-11-29 16:09:04

    编译通过...

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

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

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

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

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

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

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

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

    提交了10来次,就因为忘了判断连线经过缺口的某个顶点时的情况了。

    细节决定成败

    写完了觉得还是不算难,就是构图时麻烦了点,最短路随便找个算法都行了,我用floyd都能秒杀。

  • 0
    @ 2008-11-09 17:23:46

    帮忙看看哪儿有错啊,我觉得不会有问题么

    用map存两点间距离,s存两点是否能直接相连,添加0和4*n+1两个点

    用dijiskla算距离,最后输出map[0,4*n+1]

    有错么?怎么只过两组?

    var

    map:array[0..500,0..500]of real;

    s:array[0..500,0..500]of boolean;

    n:integer;

    {=============}

    procedure init;

    var i,j,k,a,b:integer;

    x1,x2,x3,y1,y2,y3:real;

    x,y:array[0..500]of real;

    qiangx:array[1..200]of real;

    qiangy:array[1..200,1..4]of real;

    begin

    readln(n);

    for i:=1 to n do

    begin

    read(qiangx[i]);

    for j:=1 to 4 do read(qiangy);

    end;

    x[0]:=0;y[0]:=5;x[4*n+1]:=10;y[4*n+1]:=5;

    for i:=1 to n do

    for j:=1 to 4 do

    begin

    x[4*i-4+j]:=qiangx[i];

    y[4*i-4+j]:=qiangy;

    end;

    fillchar(s,sizeof(s),true);

    for i:=0 to 4*n+1 do

    for j:=i to 4*n+1 do

    if (i+3)div 4 =(j+3)div 4 then s:=false

    else begin

    a:=(i+3)div 4;b:=(j+3)div 4;

    x1:=x[i];x2:=x[j];

    y1:=y[i];y2:=y[j];

    for k:=a+1 to b-1 do

    begin

    x3:=qiangx[k];

    y3:=y1+(y3-y1)*(y2-y1)/(x2-x1);

    if not(( (y3>qiangy[k,1]) and (y3qiangy[k,3]) and (y3

  • 0
    @ 2008-10-29 17:03:41

    为什么我做的有的错了呢!~~~~~~~~~~~~~

    才33分

  • 0
    @ 2008-10-23 21:34:56

    加两面墙+o(4*(n+2))DP+枚举DP点与前面的所有点的可行性=o(n^2*20)的算法

    =.......................秒杀?!?!?!?!

    对于数据质疑中

    for i:=1 to n+1 do

    for j:=1 to 4 do

    begin

    f:=99999;

    for k:=i-1 downto 0 do

    for l:=1 to 4 do

    if able(i,j,k,l) then

    begin

    ff:=sqrt(sqr(x[i]-x[k])+sqr(y-y[k,l]));

    f:=min(f,f[k,l]+ff);

    end;

    end;

    end.

  • 0
    @ 2008-09-30 15:40:17

    WA了N次,精度有问题

    编译通过...

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

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

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

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

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

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

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

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

  • 0
    @ 2008-09-22 20:00:48

    real和extended有什么差别啊?要怎么用呢?为什么我用real错了第四个点,用了extended却错了第一和第五个点!!!

  • 0
    @ 2008-09-17 21:19:05

    编译通过...

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

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

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

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

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

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

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

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

    floyed+直线解析式

  • 0
    @ 2008-09-02 23:08:05

    c++怎么保留到小数点后2位?prescision()只能设置有效数字,不能固定保留到小数点后几位。用c++的大牛指点下。

  • 0
    @ 2008-08-06 21:41:08

    这个题数据小,可以用三次方算法的,绝对0ms!

    (即三次方直线判断相交,再三次方的弗洛伊德,就是为着打字方便~)

    我只打了64行,全部数据0ms,算法如上……

    大家放心地做吧~

  • 0
    @ 2008-08-06 18:51:02

    哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈

    编译通过...

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

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

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

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

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

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

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

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

信息

ID
1013
难度
6
分类
计算几何 点击显示
标签
(无)
递交数
2251
已通过
526
通过率
23%
被复制
12
上传者