402805: GYM100885 F Светофоры

Вы — министр транспорта в Тридевятом королевстве. Дороги, как известно, являются одной из основных проблем королевства, тем не менее, недавно была закончена постройка Великого Королевского Тракта — самой длинной дороги в Тридевятом царстве. Тракт представляет из себя прямую дорогу, поэтому далее будем называть координатой точки на тракте расстояние от начала тракта до нее.

Вам стало известно, что король скоро собирается проехать по этому тракту от начала до конца, причем поедет он со скоростью 1. Когда именно он собирается начать, вам неизвестно, но зато вы уверены, что это произойдет в какой-то случайный целочисленный момент времени между t₁ и t₂ включительно. В рамках модернизационной программы вы отдали поручение построить на Тракте n светофоров, которые должны будут впечатлить проезжающего короля. Светофоры в некотором смысле одноразовые, а именно они поначалу горят зеленым, затем красным, а потом снова зеленым, не переключаясь больше, пока не сломаются (но можно считать, что сломаются они не скоро). Про каждый светофор вам известно три величины: его положение на Тракте, время, когда он загорится красным, и время, когда он вновь загорится зеленым. Так получилось, что последний светофор стоит прямо на конце Тракта. Понятно, что король не станет подавать плохой пример подданным: никакой светофор он не будет проезжать на красный свет (в том числе это относится и к последнему светофору). В момент, когда красный свет только загорается, ехать уже становится нельзя, а когда загорается зеленый — сразу же можно.

Ваша премия как министра напрямую зависит от того, насколько долго король будет ехать по тракту, поэтому вас интересует вопрос, сколько в среднем времени ему потребуется на то, чтоб проехать Тракт от начала до конца (включая время ожидания на последнем светофоре, если это потребуется). Напишите программу, которая посчитает эту величину.

В первой строке входного файла вводится число n — количество светофоров (1 ≤ n ≤ 100 000). Затем в каждой из следующих n строк — описания светофоров. В каждой из них содержатся 3 целых числа x_i, s_i, f_i (0 ≤ x_i, s_i, f_i ≤ 10⁹), описывающих очередной светофор: x_i — это положение светофора на Тракте, s_i — момент времени, когда светофор загорится красным, f_i — момент времени, когда он вновь загорится зеленым (0 ≤ s_i < f_i). Светофоры упорядочены по величине x, т.е. для любых номеров i и j таких, что 1 ≤ i < j ≤ n, верно, что x_i < x_j. Кроме того, гарантируется, что длина Тракта больше нуля, т.е. что x_n > 0.

В последней строке задаются целые числа t₁ и t₂  — начальный и конечный момент времени, когда король может начать свой путь (0 ≤ t₁ ≤ t₂ ≤ 10⁹).

Выведите одно число — время в пути, усредненное по всем возможным временам начала (т.е. среднее арифметические времен в пути, вычисленных для всех возможных целочисленных времен старта от t₁ до t₂ включительно). Ваш ответ будет считаться верным, если его относительная погрешность будет не более 10^- 9. Это обозначает, что, если ваш ответ равен a, а правильный — b, то должно выполняться |a - b| ≤ 10^- 9b.

2
4 11 12
8 14 15
6 9

8.5000000000

В примере король может выехать в любой момент между 6 и 9 включительно.

Если король выезжает в момент времени 6, то к первому светофору он подъезжает в момент времени 10, этот светофор еще горит зеленым, поэтому король едет дальше без остановки. Ко второму светофору король подъезжает в момент времени 14, этот светофор в этот момент загорается красным, поэтому король ждет до момента времени 15, когда светофор загорается опять зеленым. Итого получается время в пути равно 9.

Если король выезжает в момент времени 7, то к первому светофору он подъезжает в момент времени 11, когда этот светофор только загорелся красным — король ждет до момента времени 12. Ко второму светофору король подъезжает в момент времени 16, когда этот светофор уже горит зеленым. Итого получается время в пути равно 9.

Если король выезжает в момент времени 8 или 9, то он не ждет ни на одном светофоре, и время в пути получается 8.

Итого среднее время в пути есть (9 + 9 + 8 + 8) / 4 = 8.5.