Submission #1241658

---

Source Code Expand

N = int(input())
start, goal = map(int,input().split())
input()

le = []
ri = []

for i in range(N-1):
	l, r = map(int,input().split())
	le.append(l)
	ri.append(r)

le.append(goal)
ri.append(goal)

lv = [[start, 0]]
rv = [[start, 0]]

lnow = start
rnow = start

lv.append([le[0]-lnow, 1])
rv.append([ri[0]-rnow, 1])

lnow = le[0]
rnow = ri[0]

for l, r in zip(le[1:], ri[1:]):
	
	if lv[-1][0]/lv[-1][1] < l - lnow:
		lp = lv.pop()
		lv.append([lp[0]+l-lnow, lp[1]+1])
	else:
		lv.append([l - lnow, 1])
	lnow = l

	if rv[-1][0]/rv[-1][1] > r - rnow:
		rp = rv.pop()
		rv.append([rp[0]+r-rnow, rp[1]+1])
	else:
		rv.append([r - rnow, 1])
	rnow = r

root = []
s1 = 0
s2 = 0
for i in range(len(lv)):
	lv[i][1] += s1
	s1 = lv[i][1]
	lv[i][0] += s2
	s2 = lv[i][0]
s1 = 0
s2 = 0
for i in range(len(rv)):
	rv[i][1] += s1
	s1 = rv[i][1]
	rv[i][0] += s2
	s2 = rv[i][0]

lp = 1
rp = 1
mid = []
while lp<len(lv) and rp<len(rv):
	if lv[lp][1] < rv[rp][1]:
		if rv[rp-1][0]+(rv[rp][0]-rv[rp-1][0])/(rv[rp][1]-rv[rp-1][1])*(lv[lp][1] - rv[rp-1][1]) <= lv[lp][0]:
			mid.append(lv[lp])
			rv[rp-1] = lv[lp]
		lp += 1
	else:
		if lv[lp-1][0]+(lv[lp][0]-lv[lp-1][0])/(lv[lp][1]-lv[lp-1][1])*(rv[rp][1] - lv[lp-1][1]) >= rv[rp][0]:
			mid.append(rv[rp])
			lv[lp-1] = rv[rp]
		rp += 1

res = 0
now = [start, 0]

from math import sqrt

for i in mid:
	res += sqrt((i[0]-now[0])**2 + (i[1]-now[1])**2)
	now = i

print(res)

Submission Info

Judge Result