Problem:


Vampire

Mr. C is a vampire. If he is exposed to the sunlight directly, he turns 
into ash.
Nevertheless, last night, he attended to the meeting of Immortal and 
Corpse Programmers
Circle, and he has to go home in the near dawn.
Fortunately, there are many tall buildings around Mr. C's home, and 
while the sunlight is blocked by the buildings, he can move around 
safely.
The top end of the sun has just reached the horizon now.
In how many seconds does Mr. C have to go into his safe coffin?

To simplify the problem, we represent the eastern dawn sky as a 2-dimensional
x-y plane, where the x axis is horizontal and the y axis
is vertical, and approximate building silhouettes by rectangles
and the sun by a circle on this plane.

The x axis represents the horizon.
We denote the time by t, and the current time is t=0.
The radius of the sun is r and
its center is at (0, -r) when the time t=0.
The sun moves on the x-y plane in a uniform linear motion at
a constant velocity of (0, 1) per second.

The sunlight is blocked if and only if the entire region of the sun 
(including its edge) is included in the union of the silhouettes 
(including their edges) and the region below the horizon (y &#8804; 0).

Write a program that computes the time of the last moment when the sunlight is blocked.

The following figure shows the layout of silhouettes and the position of the sun at
the last moment when the sunlight is blocked, that corresponds to the
first dataset of Sample Input below. As this figure indicates, there are possibilities
that the last moment when the sunlight is blocked can be the time t=0.

The sunlight is blocked even when two silhouettes share parts of their edges.

The following figure shows the layout of silhouettes and the position of the sun at the
last moment when the sunlight is blocked, corresponding to the second
dataset of Sample Input.
In this dataset the radius of the sun is 2 and there are two silhouettes:
the one with height 4 is in -2 &#8804; x &#8804; 0, and
the other with height 3 is in 0 &#8804; x &#8804; 2.

Input

The input consists of multiple datasets.
The first line of a dataset contains two
integers r and n separated by a space.
r is the radius of the sun and n is the number of silhouettes
of the buildings.
(1 &#8804; r &#8804; 20, 0 &#8804; n &#8804; 20)

Each of following n lines contains three integers
xli, xri, hi (1 &#8804; i &#8804; n) separated by a space.

These three integers represent a silhouette rectangle of a building.
The silhouette rectangle is parallel to the horizon, and its left and right edges
are at x = xli and x = xri, its top
edge is at y = hi, and its bottom edge is on
the horizon.
(-20 &#8804; xli < xri &#8804; 20,
0 < hi &#8804; 20)

The end of the input is indicated by a line containing two zeros separated by a space.

Note that these silhouettes may overlap one another.

Output

For each dataset, output a line containing the number indicating the time t of the last moment when the sunlight is blocked.
The value should not have an error greater than 0.001.
No extra characters should appear in the output.

Sample Input

2 3
-2 -1 3
0 1 3
2 3 3
2 2
-2 0 4
0 2 3
2 6
-3 3 1
-2 3 2
-1 3 3
0 3 4
1 3 5
2 3 6
2 6
-3 3 1
-3 2 2
-3 1 3
-3 0 4
-3 -1 5
-3 -2 6
0 0

Output for the Sample Input

0.0000
3.0000
2.2679
2.2679



Sample input:
2 3
-2 -1 3
0 1 3
2 3 3
2 2
-2 0 4
0 2 3
2 6
-3 3 1
-2 3 2
-1 3 3
0 3 4
1 3 5
2 3 6
2 6
-3 3 1
-3 2 2
-3 1 3
-3 0 4
-3 -1 5
-3 -2 6
0 0


Sample output:
0.0000
3.0000
2.2679
2.2679

Submission status: Wrong Answer

Solution code:
while 1:
    r,n = map(int,raw_input().split())
    if r == 0: break

    h = [0]*43
    for loop in xrange(n):
        xl,xr,hi = map(int,raw_input().split())
        for i in xrange(xl+21,xr+21): h[i] = max(h[i],hi)
    hu,hd = h[:],h[:]
    for i in xrange(1,43):
        if h[i-1] != h[i]:
            hu[i] = max(h[i-1],h[i])
            hd[i] = min(h[i-1],h[i])
            
    y,d,u = 0.,-r,r
    for loop in xrange(30):
        if any((x-21)**2+(y-hd[x])**2 < r**2 for x in xrange(1,42)):
            u = y
        else:
            d = y
        y = (u+d)/2
    print "%.5f"%(y+r)

Submission status: Wrong Answer

Solution code:
while 1:
    r,n = map(int,raw_input().split())
    if r == 0: break

    h = [0]*43
    for loop in xrange(n):
        xl,xr,hi = map(int,raw_input().split())
        for i in xrange(xl+21,xr+21): h[i] = max(h[i],hi)
    hu,hd = h[:],h[:]
    for i in xrange(1,43):
        if h[i-1] != h[i]:
            hu[i] = max(h[i-1],h[i])
            hd[i] = min(h[i-1],h[i])
            
    y,d,u = 0.,-r,r
    for loop in xrange(30):
        if any((x-21)**2+min((y-hd[x])**2,(y-hu[x]))**2 < r**2 for x in xrange(1,42)):
            u = y
        else:
            d = y
        y = (u+d)/2
    print "%.5f"%(y+r)

Submission status: Wrong Answer

Solution code:
while 1:
    r,n = map(int,raw_input().split())
    if r == 0: break

    h = [0]*43
    for loop in xrange(n):
        xl,xr,hi = map(int,raw_input().split())
        for i in xrange(xl+21,xr+21): h[i] = max(h[i],hi)
    hu,hd = h[:],h[:]
    for i in xrange(1,43):
        if h[i-1] != h[i]:
            hu[i] = max(h[i-1],h[i])
            hd[i] = min(h[i-1],h[i])
            
    y,d,u = 0.,-r,r
    for loop in xrange(30):
        for x in xrange(1,43):
            if (x-21)**2+(y-hu[x])**2 < r**2 or (x-21)**2+(y-hd[x])**2 < r**2:
                u = y
                break
        else:
            d = y
        y = (u+d)/2
    print "%.5f"%(y+r)

Submission status: Wrong Answer

Solution code:
while 1:
    r,n = map(int,raw_input().split())
    if r == 0: break

    h = [0]*43
    for loop in xrange(n):
        xl,xr,hi = map(int,raw_input().split())
        for i in xrange(xl+21,xr+21): h[i] = max(h[i],hi)
    hu,hd = h[:],h[:]
    for i in xrange(1,43):
        if h[i-1] != h[i]:
            hu[i] = max(h[i-1],h[i])
            hd[i] = min(h[i-1],h[i])
            
    y,d,u = 0.,-r,r
    for loop in xrange(30):
        for x in xrange(1,43):
            if (x-21)**2+(y-hu[x])**2 < r**2 or (x-21)**2+(y-hd[x])**2 < r**2:
                u = y
                break
        else:
            d = y
        y = (u+d)/2
    print "%.4f"%(y+r)

Submission status: Wrong Answer

Solution code:
from math import sqrt
def calc(x, h):
    return max(h+r-sqrt(r**2 - x**2), 0)
while 1:
    r, n = map(int, raw_input().split())
    if r == 0:
        break
    H = [0]*41
    for i in xrange(n):
        xl, xr, h = map(int, raw_input().split())
        for j in xrange(xl, xr):
            H[j] = max(H[j], h)
    ans = 10**9
    for i in xrange(-r, r):
        print i, H[i], calc(i, H[i]), calc(i+1, H[i])
        ans = min(ans, calc(i, H[i]), calc(i+1, H[i]))
    print "%.6f" % ans

Submission status: Wrong Answer

Solution code:
import sys

EPS = 1e-9

def normalize(x):
    return 2 * (x + 20)

def check(seg, r, t):

    for x in range(40 - r, 40 + r + 1):
        ok = False
        for s in seg:
            if s[2] < t - r:
                #print("over!!!! x:{}, s[2]:{}, t-r:{}",x,s[2],t-r)
                return False
            if s[0] <= x and x <= s[1]:
                k1 = (s[0] - 40)**2 + (s[2] - (t - r))**2
                k2 = (s[1] - 40)**2 + (s[2] - (t - r))**2
                #print("\tx:{}\ts[2]:{}\tt/2:{}\tr:{}\tk1:{}\tk2:{}\tkk:{}".format(x, s[2], t/2, r, k1, k2,kk))
                if k1 >= r*r and k2 >= r*r:
                    ok = True
                    break

        if not ok:
            return False

    return True

def main():

    while True:
        r,n = map(int, sys.stdin.readline().split())
        if r == 0 and n == 0:
            break

        seq = [0] * 100 # 2?????§?¨??????????
        for i in range(n):
            x1,x2,h = map(int, sys.stdin.readline().split())
            for x in range(normalize(x1), normalize(x2) + 1):
                seq[x] = max(seq[x], 2*h)

        prev = 0
        st = 0
        seg = []
        for i in range(100):
            if prev != seq[i]:
                if i % 2 == 0 :
                    seg.append( [st, i, prev] )
                    st = i
                else:
                    seg.append( [st, i - 1, prev] )
                    st = i - 1
                prev = seq[i]

        # ????????????????????¨?????????????????????????????????????????§?????????append?????????
        # ??????1??\?????????????????\???
        r *= 2
        seg = [ x for x in seg if x[2] > 0 and (40 - r <= x[0] or x[1] <= 40 + r)]

        # ????????§?¨???????????????????????????????????????????????????????
        for i in range(len(seg) - 1):
            if seg[i][1] == seg[i + 1][0]:
                if seg[i][2] > seg[i + 1][2]:
                    seg[i + 1][0] += EPS
                elif seg[i][2] < seg[i + 1][2]:
                    seg[i][1] -= EPS
        
        #print(seg)

        tl = 0.0
        tr = 40.0
        for k in range(60):
            tm = (tr + tl) / 2.0
            if check(seg, r, tm):
                tl = tm
            else:
                tr = tm

        print("{0:.4f}".format(tl / 2))




if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())

def calc(p,x):
    return p*(100+x)//100


while True:
    r,n = inpl()
    if r == 0:
        break
    else:
        heights = defaultdict(int)
        ans = INF
        for _ in range(n):
            xl,xr,h = inpl()
            heights[xl+0.1] = max(heights[xl+0.1],h)
            heights[xr-0.1] = max(heights[xr-0.1],h)
            for x in range(xl+1,xr):
                heights[x-0.1] = max(heights[x-0.1],h)
                heights[x+0.1] = max(heights[x+0.1],h)

        for x in range(-23,23):
            h = min(heights[x-0.1],heights[x+0.1])
            #print(x,h)
            if r > abs(x):
                tmp = h - (r**2-x**2)**(1/2)
                ans = min(ans,tmp+r)
        print(ans)

Submission status: Accepted

Solution code:
import math

while True:
  (r, n) = map(int, raw_input().split())
  if r + n == 0: break

  hs = {}
  for i in range(-22, 22 + 1):
    hs[i] = 0

  for _ in range(n):
    (xl, xr, h) = map(int, raw_input().split())
    for i in range(xl, xr):
      hs[i] = max(hs[i], h)

  ans = 10 ** 9
  for i in range(-r, r):
    p = i
    if i < 0: p += 1
    rr = hs[i] + r - math.sqrt(r * r - p * p)
    ans = min(ans, rr)

  print "%.10f" % max(0, ans)

Submission status: Accepted

Solution code:
while 1:
    r,n = map(int,raw_input().split())
    if r == 0: break

    h = {i:0 for i in xrange(-21,21)}
    for loop in xrange(n):
        xl,xr,hi = map(int,raw_input().split())
        for i in xrange(xl,xr):
            h[i] = max(h[i],hi)

    for i in xrange(20,-21,-1):
        h[i] = min(h[i-1],h[i])

    y,d,u = 0,-r,h[0]-r
    for loop in xrange(30):
        if any(x**2+(y-h[x])**2 < r**2 for x in xrange(-20,21)):
            u = y
        else:
            d = y
        y = (d+u)/2.
    print "%.4f"%abs(y+r)

Submission status: Accepted

Solution code:
from math import sqrt
def calc(x, h):
    return max(h+r-sqrt(r**2 - x**2), 0)
while 1:
    r, n = map(int, raw_input().split())
    if r == 0:
        break
    H = [0]*41
    for i in xrange(n):
        xl, xr, h = map(int, raw_input().split())
        for j in xrange(xl, xr):
            H[j] = max(H[j], h)
    ans = 10**9
    for i in xrange(-r, r):
        ans = min(ans, calc(i, H[i]), calc(i+1, H[i]))
    print "%.6f" % ans

Submission status: Accepted

Solution code:
import sys
import math

OFFSET = 20

def main():

    while True:
        r,n = map(int, sys.stdin.readline().split())
        if r == 0 and n == 0:
            break

        seq = [0] * 40
        for i in range(n):
            x1,x2,h = map(int,sys.stdin.readline().split())
            for k in range(x1, x2):
                seq[k + OFFSET] = max(seq[k + OFFSET], h)

        # ??????????????§??????????????? => ??????????????????????????¶??????????????°??????????????¶????????????
        # seq[x] = [x,x+1]?????????h?????¨???
        ans = 9999999999
        for x in range(-r+1, r):
            y = min(seq[x + OFFSET - 1], seq[x + OFFSET])
            t = y + r - math.sqrt(r*r - x*x) # ???????????\????????????
            #print("r:{}\tx:{}\tx[]:{}\ty:{}\tt:{}".format(r,x,seq[x + OFFSET],y,t))
            ans = min(ans, t)

        print("{0:.4f}".format(ans))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
while True:
    R, N = map(int, input().split())
    if not (R | N):
        break
    geta = 20
    buildings = [0] * (geta * 2)
    for _ in range(N):
        xl, xr, h = map(int, input().split())
        for i in range(xl + geta, xr + geta):
            buildings[i] = max(buildings[i], h)

    left, right = 0, 20
    for _ in range(100):
        mid = (left + right) / 2
        flag = True
        for i in range(-R + geta, R + geta):
            if i < geta:
                y = pow(R * R - (i - geta + 1) * (i - geta + 1), 0.5)
                flag &= buildings[i] >= y - R + mid
            else:
                y = pow(R * R - (i - geta) * (i - geta), 0.5)
                flag &= buildings[i] >= y - R + mid
        if flag:
            left = mid
        else:
            right = mid
    print("{:.20f}".format(left))

Submission status: Accepted

Solution code:
while True:
    R, N = map(int, input().split())
    if not (R | N):
        break
    geta = 20
    buildings = [0] * (geta * 2)
    for _ in range(N):
        xl, xr, h = map(int, input().split())
        for i in range(xl + geta, xr + geta):
            buildings[i] = max(buildings[i], h)

    left, right = 0, 20
    while right - left > 1e-4:
        mid = (left + right) / 2
        flag = True
        for i in range(-R + geta, R + geta):
            if i < geta:
                y = pow(R * R - (i - geta + 1) * (i - geta + 1), 0.5)
                flag &= buildings[i] >= y - R + mid
            else:
                y = pow(R * R - (i - geta) * (i - geta), 0.5)
                flag &= buildings[i] >= y - R + mid
        if flag:
            left = mid
        else:
            right = mid
    print("{:.20f}".format(left))

Submission status: Accepted

Solution code:
while True:
    R, N = map(int, input().split())
    if not (R | N):
        break
    geta = 20
    buildings = [0] * (geta * 2)
    for _ in range(N):
        xl, xr, h = map(int, input().split())
        for i in range(xl + geta, xr + geta):
            buildings[i] = max(buildings[i], h)

    sun = [0] * (geta * 2)
    for i in range(-R + geta, R + geta):
        if i < geta:
            buildings[i] -= pow(R * R - (i - geta + 1) * (i - geta + 1), 0.5) - R
        else:
            buildings[i] -= pow(R * R - (i - geta) * (i - geta), 0.5) - R


    left, right = 0, 20
    while right - left > 1e-4:
        mid = (left + right) / 2
        flag = True
        for i in range(-R + geta, R + geta):
            if i < geta:
                flag &= buildings[i] >= mid
            else:
                y = pow(R * R - (i - geta) * (i - geta), 0.5)
                flag &= buildings[i] >= mid
        if flag:
            left = mid
        else:
            right = mid
    print("{:.20f}".format(left))

Submission status: Accepted

Solution code:
while True:
    R, N = map(int, input().split())
    if not (R | N):
        break
    geta = 20
    buildings = [0] * (geta * 2)
    for _ in range(N):
        xl, xr, h = map(int, input().split())
        for i in range(xl + geta, xr + geta):
            buildings[i] = max(buildings[i], h)

    ans = 20
    for i in range(-R + geta, R + geta):
        if i < geta:
            buildings[i] -= pow(R * R - (i - geta + 1) * (i - geta + 1), 0.5) - R
        else:
            buildings[i] -= pow(R * R - (i - geta) * (i - geta), 0.5) - R
        ans = min(ans, buildings[i])
    print(ans)

Submission status: Accepted

Solution code:
while True:
    R, N = map(int, input().split())
    if not (R | N):
        break
    geta = 20
    buildings = [0] * (geta * 2)
    for _ in range(N):
        xl, xr, h = map(int, input().split())
        for i in range(xl + geta, xr + geta):
            buildings[i] = max(buildings[i], h)

    print(min(buildings[i] - pow(R ** 2 - (i - geta + (i < geta)) ** 2, 0.5) + R for i in range(-R + geta, R + geta)))

Submission status: Accepted

Solution code:
from math import sqrt
while True:
    R, N = map(int, input().split())
    if not (R | N):
        break
    geta = 20
    buildings = [0] * (geta * 2)
    for _ in range(N):
        xl, xr, h = map(int, input().split())
        for i in range(xl + geta, xr + geta):
            buildings[i] = max(buildings[i], h)

    print(min(buildings[i] - sqrt(R * R - (i - geta + (i < geta)) * (i - geta + (i < geta))) + R for i in range(-R + geta, R + geta)))

Submission status: Accepted

Solution code:
import math

def ri(): return int(input())
def rli(): return list(map(int, input().split()))

r, n = rli()
while(r != 0):
    shade = [0 for i in range(41)]
    shade[40] = 1145148101919
    t = [1145148101919 for i in range(41)]
    for i in range(n):
        xl, xr, h = rli()
        for j in range(xl+20, xr+20):
            shade[j] = max(shade[j], h)
    shade[20-r-1] = 1145148101919
    shade[20+r] = 1145148101919

    for i in range(20-r, 20+r+1):
        x = 20-i
        t[i] = min(shade[i-1], shade[i]) - math.sqrt(r**2 - x**2) + r

    print(min(t))
    r, n = rli()

Submission status: Accepted

Solution code:
#!/usr/bin/env python
from math import *

while True:
    r, n = map(int, raw_input().split())
    if r == 0:
        break

    m = {}
    for i in range(-50, 50):
        m[i] = 0

    for loop in range(n):
        x1, x2, h = map(int, raw_input().split())
        for i in range(x1, x2):
            m[i] = max(m[i], h)

    ans = 100
    for i in range(-r, 0):
        rem = r - sqrt(r * r - (i + 1) * (i + 1)) + m[i]
        ans = min(rem, ans)

    for i in range(0, r):
        rem = r - sqrt(r * r - i * i) + m[i]
        ans = min(rem, ans)

    print ans

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 998244353
dd = [(0,-1),(1,0),(0,1),(-1,0)]
ddn = [(0,-1),(1,-1),(1,0),(1,1),(0,1),(-1,-1),(-1,0),(-1,1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    rr = []

    while True:
        r,n = LI()
        if r == 0 and n == 0:
            break
        a = [LI() for _ in range(n)]
        d = collections.defaultdict(int)
        for xl,xr,h in a:
            for x in range(xl,xr):
                if d[x] < h:
                    d[x] = h
        tr = inf
        r2 = r**2
        for x in range(-r,r):
            h = d[x]
            k = min(abs(x), abs(x+1))
            t = (r2 - k**2) ** 0.5
            xr = r - t + h
            if tr > xr:
                tr = xr

        rr.append('{:0.9f}'.format(tr))

    return '\n'.join(map(str,rr))


print(main())

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from math import sqrt
def inpl(): return list(map(int, input().split()))
R, N = inpl()
while R:
    H = [0] * 41
    r0 = 0
    l0 = 0
    for _ in range(N):
        l, r, h = inpl()
        if l < 0 and r >= 0:
            l0 = max(l0, h)
        if l <= 0 and r > 0:
            r0 = max(r0, h)

        l += (l <= 0)
        r -= (r >= 0)

        for i in range(l, r+1):
            if i != 0:
                H[i+20] = max(H[i+20], h)
    H[20] = min(l0, r0)
    ans = 20
    for x in range(-R+1, R):
        time = R - sqrt(R**2 - x**2) + H[x+20]
        ans = min(ans, time)
    print(ans)
    R, N = inpl()

Submission status: Accepted

Solution code:
import math

while True:
    r, n = map(int, input().split())
    if r == 0 and n == 0:
        break
    sun_place = [-10000000000000000000 for _ in range(r)]
    for i in range(r):
        sun_place[i] = 0 - r + math.sqrt(r * r - i * i)

    ans = 10000000000000000
    bilding1 = [0 for i in range(len(sun_place))]
    bilding2 = [0 for i in range(len(sun_place))]
    for i in range(n):
        x1, x2, h = map(int, input().split())
        if x1 < -r:
            x1 = -r
        if r <= x2:
            x2 = r
        for j in range(x1, x2):
            if j < 0:
                j += 1
                bilding1[abs(j)] = max(h, bilding1[abs(j)])
            else:
                bilding2[abs(j)] = max(h, bilding2[abs(j)])

    for i in range(len(sun_place)):
        ans = min(ans, bilding1[i] - sun_place[i])
        ans = min(ans, bilding2[i] - sun_place[i])
    print(ans)
    # print(bilding1, bilding2)
    # print(sun_place)

Submission status: Accepted

Solution code:
from collections import defaultdict
# -*- coding: utf-8 -*-
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


def main():
    rr = []

    while True:
        r, n = map(int, input().split())

        if r == 0 and n == 0:
            break
        a = [list(map(int, input().split())) for _ in range(n)]

        d = defaultdict(int)
        for xl, xr, h in a:
            for x in range(xl, xr):
                if d[x] < h:
                    d[x] = h

        tr = float('inf')
        r2 = r**2
        for x in range(-r, r):
            h = d[x]
            k = min(abs(x), abs(x+1))
            t = (r2-k**2) ** 0.5
            xr = r-t+h
            if tr > xr:
                tr = xr
        rr.append('{:0.9f}'.format(tr))

    return '\n'.join(map(str, rr))


print(main())

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    while True:
        n = II()
        if not n:
            break
        a = IR(n)
        a.sort()
        print(sum(a[1:-1])//(n-2))
            
    return

#B
def B():
    move = [[1, 0], [-1, 0], [0, 1], [0, -1]]
    while True:
        w, h = LI()
        if w == h == 0:
            break
        field = SR(2 * h - 1)
        check = [[True] * (2 * w - 1) for i in range(2 * h - 1)]
        next = deque()
        next.append((0, 0))
        ans = 1
        flg = True
        
        while next and flg:
            now = next
            next = deque()
            while now:
                x, y = now.pop()
                for mx, my in move:
                    mmx, mmy = x + mx, y + my
                    if 0 <= mmx < 2 * w - 1 and 0 <= mmy < 2 * h - 1:
                        if field[mmy][mmx] == '0' and check[mmy+my][mmx+mx]:
                            next.append((mmx + mx, mmy + my))
                            check[mmy + my][mmx + mx] = False
                            if mmx+mx == 2 * w - 2 and mmy+my == 2 * h - 2:
                                print(ans+1)
                                flg = False
                                next = deque()
                                now = deque()
                                break
            ans += 1
        if flg:
            print(0)
    return

#C
def C():
    while 1:
        r, n = LI()
        if r == n == 0:
            break
        lis = [0 for i in range(2 * r)]
        ans = inf
        for _ in range(n):
            xl, xr, h = LI()
            for i in range(2 * r):
                if xl+r <= i < xr+r:
                    lis[i] = max(lis[i], h)
        for i in range(2 * r):
            if i < r:
                ans = min(ans, r - math.sqrt((r ** 2 - (r - i - 1)** 2)) + lis[i])
            else:
                ans = min(ans, r - math.sqrt((r ** 2 - (r - i)** 2)) + lis[i])
        print(ans)
    return

#D
def D():
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == '__main__':
    C()

Submission status: Accepted

Solution code:

#C
while 1:
    r,n = map(int, input().split())
    if r == n == 0:break
    ans = [[float("inf") for i in range(100)] for j in range(100)]
    for y in range(100):
        for j in range(2*r):
            x = j-r
            if x < 0:
                x += 1
            ans[y][j] = r+y-(r**2-x**2)**0.5
    for i in range(n):
        a,b,h = map(int, input().split())
        for x in range(a,b):
            j = x+r
            for y in range(h):
                ans[y][j] = float("inf")
    a = float("inf")
    for i in ans:
        a = min(min(i),a)
    print(a)

Submission status: Accepted

Solution code:
while True:
  r, n = list(map(int, input().split()))
  if r==0:
    break

  b = [0 for i in range(60)]
  for i in range(n):
    ll, rr, x = list(map(int, input().split()))
    for j in range(ll, rr):
      b[30+j] = max(b[30+j], x)
  b[30-r-1], b[30+r] = 1e9, 1e9

  ans = 1e9
  for x in range(30-r, 30+r+1):
    t = (r**2-(x-30)**2)**(1/2)
    cur = r-t+min(b[x], b[x-1])
    ans = min(ans, cur)
  print(ans)

Submission status: Accepted

Solution code:
while 1:
    co=[0 for i in range(40)]
    r,n=map(int,input().split())
    if r==n==0:
        break
    for i in range(n):
        a,b,h=map(int,input().split())
        a+=20
        b+=20
        for j in range(a,b):
            co[j]=max(co[j],h)
    r_list=[]
    for i in range(r):
        r_list.append((r**2-i**2)**0.5+500)
    r_list=[-9999 for j in range(20-r)]+r_list[::-1]+r_list+[-9999 for j in range(20-r)]
    for i in range(40):
        if co[i]<r_list[i]:
            tmp=r_list[i]
            r_list=list(map(lambda x:x-(tmp-co[i]),r_list))
    print(r_list[20])