CF32E.Hide-and-Seek

提高+/省选-

通过率:0%

时间限制:2.00s

内存限制:256MB

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

Victor and Peter are playing hide-and-seek. Peter has hidden, and Victor is to find him. In the room where they are playing, there is only one non-transparent wall and one double-sided mirror. Victor and Peter are points with coordinates (x__v, y__v) and (x__p, y__p) respectively. The wall is a segment joining points with coordinates (x__w, 1, y__w, 1) and (x__w, 2, y__w, 2), the mirror — a segment joining points (x__m, 1, y__m, 1) and (x__m, 2, y__m, 2).

If an obstacle has a common point with a line of vision, it's considered, that the boys can't see each other with this line of vision. If the mirror has a common point with the line of vision, it's considered, that the boys can see each other in the mirror, i.e. reflection takes place. The reflection process is governed by laws of physics — the angle of incidence is equal to the angle of reflection. The incident ray is in the same half-plane as the reflected ray, relative to the mirror. I.e. to see each other Victor and Peter should be to the same side of the line, containing the mirror (see example 1). If the line of vision is parallel to the mirror, reflection doesn't take place, and the mirror isn't regarded as an obstacle (see example 4).

Victor got interested if he can see Peter, while standing at the same spot. Help him solve this problem.

维克多和彼得正在玩捉迷藏。彼得已经藏好,维克多需要找到他。他们玩耍的房间中只有一堵不透明的墙和一面双面镜。维克多和彼得分别位于坐标为 (xv, yv)(x_v,\,y_v) 和 (xp, yp)(x_p,\,y_p) 的点上。墙是一条线段,其两个端点坐标分别为 (xw,1, yw,1)(x_{w,1},\,y_{w,1}) 和 (xw,2, yw,2)(x_{w,2},\,y_{w,2});镜子也是一条线段,其两个端点坐标分别为 (xm,1, ym,1)(x_{m,1},\,y_{m,1}) 和 (xm,2, ym,2)(x_{m,2},\,y_{m,2})。

若视线(即连接两点的直线)与某一障碍物存在公共点,则认为该视线被阻挡,两名男孩无法通过此视线彼此看见。若视线与镜子存在公共点,则认为两人可通过镜子彼此看见,即发生反射。反射过程遵循物理定律:入射角等于反射角;且入射光线与反射光线位于镜面所在直线的同一侧(即:为能通过镜子彼此看见,维克多和彼得必须位于包含镜子的直线的同一侧;参见示例 1)。若视线与镜子所在直线平行,则不发生反射,且镜子不被视为障碍物(参见示例 4)。

维克多好奇:当他站在原地不动时,是否能看到彼得?请帮助他解决这个问题。

输入格式

The first line contains two numbers x__v and y__v — coordinates of Victor.

The second line contains two numbers x__p and y__p — coordinates of Peter.

The third line contains 4 numbers x__w, 1, y__w, 1, x__w, 2, y__w, 2 — coordinates of the wall.

The forth line contains 4 numbers x__m, 1, y__m, 1, x__m, 2, y__m, 2 — coordinates of the mirror.

All the coordinates are integer numbers, and don't exceed 104 in absolute value. It's guaranteed, that the segments don't have common points, Victor and Peter are not on any of the segments, coordinates of Victor and Peter aren't the same, the segments don't degenerate into points.

第一行包含两个数 xvx_v 和 yvy_v — Victor 的坐标。
第二行包含两个数 xpx_p 和 ypy_p — Peter 的坐标。
第三行包含四个数 xw,1x_{w,1}、yw,1y_{w,1}、xw,2x_{w,2}、yw,2y_{w,2} — 墙壁的端点坐标。
第四行包含四个数 xm,1x_{m,1}、ym,1y_{m,1}、xm,2x_{m,2}、ym,2y_{m,2} — 镜子的端点坐标。

所有坐标均为整数,且其绝对值不超过 10410^4。保证线段之间无公共点,Victor 和 Peter 均不位于任一线段上,Victor 与 Peter 的坐标不相同,且所有线段均不退化为点。

输出格式

Output YES, if Victor can see Peter without leaving the initial spot. Otherwise output NO.

如果维克多无需离开初始位置就能看到彼得,则输出 YES;否则输出 NO。

输入输出样例

  • 输入#1

    -1 3
    1 3
    0 2 0 4
    0 0 0 1

    输出#1

    NO
  • 输入#2

    0 0
    1 1
    0 1 1 0
    -100 -100 -101 -101

    输出#2

    NO
  • 输入#3

    0 0
    1 1
    0 1 1 0
    -1 1 1 3

    输出#3

    YES
  • 输入#4

    0 0
    10 0
    100 100 101 101
    1 0 3 0

    输出#4

    YES

输入解题思路,AI测评打分。不知道怎么写?

首页