Problem:


Problem E: Safe Area

Nathan O. Davis is challenging a kind of shooter game. In this game, enemies emit laser beams
from outside of the screen. A laser beam is a straight line with a certain thickness. Nathan
moves a circular-shaped machine within the screen, in such a way it does not overlap a laser
beam. As in many shooters, the machine is destroyed when the overlap happens.

Nathan is facing an uphill stage. Many enemies attack simultaneously in this stage, so eventually
laser beams fill out almost all of the screen. Surprisingly, it is even possible he has no "safe area" on the screen. In other words, the machine cannot survive wherever it is located in some
cases.

The world is as kind as it is cruel! There is a special item that helps the machine to survive
any dangerous situation, even if it is exposed in a shower of laser beams, for some seconds. In
addition, another straight line (called "a warning line") is drawn on the screen for a few seconds
before a laser beam is emit along that line.

The only problem is that Nathan has a little slow reflexes. He often messes up the timing to
use the special item. But he knows a good person who can write a program to make up his slow
reflexes - it's you! So he asked you for help.

Your task is to write a program to make judgement whether he should use the item or not, for
given warning lines and the radius of the machine.

Input

The input is a sequence of datasets. Each dataset corresponds to one situation with warning
lines in the following format:

       W H N R

       x1,1 y1,1 x1,2 y1,2 t1

       x2,1 y2,1 x2,2 y2,2 t2

       ...

       xN,1 yN,1 xN,2 yN,2 tN

The first line of a dataset contains four integers W, H, N and R (2 < W ≤ 640, 2 < H ≤ 480,
0 ≤ N ≤ 100 and 0 < R < min{W, H}/2). The first two integers W and H indicate the width
and height of the screen, respectively. The next integer N represents the number of laser beams.

The last integer R indicates the radius of the machine. It is guaranteed that the output would
remain unchanged if the radius of the machine would become larger by 10-5 than R.

The following N lines describe the N warning lines. The (i+1)-th line of the dataset corresponds
to the i-th warning line, which is represented as a straight line which passes through two given
different coordinates (xi,1, yi,1 ) and (xi,2 , yi,2 ). The last integer ti indicates the thickness of the
laser beam corresponding to the i-th warning line.

All given coordinates (x, y) on the screen are a pair of integers (0 ≤ x ≤ W, 0 ≤ y ≤ H). Note
that, however, the machine is allowed to be located at non-integer coordinates during the play.

The input is terminated by a line with four zeros. This line should not be processed.

Output

For each case, print "Yes" in a line if there is a safe area, or print "No" otherwise.

Sample Input

100 100 1 1
50 0 50 100 50
640 480 1 1
0 0 640 480 100
0 0 0 0

Output for the Sample Input

No
Yes



Sample input:
100 100 1 1
50 0 50 100 50
640 480 1 1
0 0 640 480 100
0 0 0 0


Sample output:
No
Yes

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
write = sys.stdout.write

def cross_point(p0, q0, p1, q1):
    x0, y0 = p0; x1, y1 = q0
    x2, y2 = p1; x3, y3 = q1
    dx0 = x1 - x0
    dy0 = y1 - y0
    dx1 = x3 - x2
    dy1 = y3 - y2

    s = (y0-y2)*dx1 - (x0-x2)*dy1
    sm = dx0*dy1 - dy0*dx1
    if sm == 0:
        return None
    return x0 + s*dx0/sm, y0 + s*dy0/sm

def solve():
    W, H, N, R = map(int, readline().split())
    if W == H == 0:
        return False
    L = [tuple(map(int, readline().split())) for i in range(N)]
    L.extend([
        (0, 0, W, 0, 0),
        (0, 0, 0, H, 0),
        (0, H, W, H, 0),
        (W, 0, W, H, 0),
    ])
    EPS = 1e-9
    pp = ((1, 1), (1, -1), (-1, 1), (-1, -1))
    for i in range(N+4):
        xi1, yi1, xi2, yi2, t0 = L[i]
        p0 = (xi1, yi1); q0 = (xi2, yi2)
        dx0 = (xi2 - xi1); dy0 = (yi2 - yi1)
        d0 = (dx0**2 + dy0**2)**.5
        for j in range(i):
            xj1, yj1, xj2, yj2, t1 = L[j]
            p1 = (xj1, yj1); q1 = (xj2, yj2)
            dx1 = (xj2 - xj1); dy1 = (yj2 - yj1)
            d1 = (dx1**2 + dy1**2)**.5
            cp = cross_point(p0, q0, p1, q1)
            if cp is None:
                continue
            x0, y0 = cp
            sv = abs(dx0*dy1 - dx1*dy0)
            for p, q in pp:
                a = p*d1*(t1+R)
                b = q*d0*(t0+R)
                x = x0 + (a * dx0 + b * dx1) / sv
                y = y0 + (a * dy0 + b * dy1) / sv
                if not R - EPS < x < W-R + EPS or not R - EPS < y < H-R + EPS:
                    continue
                ok = 1
                for k in range(N):
                    xk1, yk1, xk2, yk2, t2 = L[k]
                    dxp = xk2 - xk1; dyp = yk2 - yk1
                    dxq = x - xk1; dyq = y - yk1
                    d2 = (dxp**2 + dyp**2)**.5
                    if abs(dxp*dyq - dxq*dyp) < (R + t2) * d2 - EPS:
                        ok = 0
                if ok:
                    write("Yes\n")
                    return True
    write("No\n")
    return True
while solve():
    ...