시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB85151227.273%

문제

시장은 새로운 TV 송신 시스템을 도입하기로 했다. 도시는 길이가 D인 선분 위에 여러 개의 빌딩이 놓여져 있는 형태이다. 빌딩의 너비는 무시할 수 있을만큼 작다. 일부 빌딩의 옥상에는 TV 송신기 있으며, 그 크기도 무시할 수 있다.

TV 송신기는 TV 신호를 모든 방향으로 전송한다. 신호는 직선으로 전송되며, 빌딩을 통과할 수 없다. 도시의 일부분은 기존에 설치된 송신기로 TV 신호를 수신할 수 있다.

TV 신호를 받을 수 있는 선분을 찾고 그 길이를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 빌딩의 수 N (1 ≤ N ≤ 3·105)과 도시의 길이 D(1 ≤ D ≤ 109)가 주어진다.

다음 N개 줄에는 i번째 빌딩의 정보를 나타내는 세 개의 정수가 주어진다.

  1. 빌딩의 옥상에 송신기가 설치된 경우에 첫 번째 정수는 1이고, 설치되지 않은 경우에는 0이다.
  2. 두 번째 정수는 빌딩이 도시의 왼쪽 끝으로부터 떨어진 거리 Xi (0 ≤ Xi ≤ D) 이다.
  3. 세 번째 정수는 빌딩의 높이 Hi (1 ≤ Hi ≤ 109) 이다.

빌딩은 왼쪽으로부터 떨어진 거리가 증가하는 순으로 주어진다. 두 빌딩이 같은 곳에 있는 경우는 없다.

출력

첫째 줄에 구한 정답을 출력한다. 오차는 최대 10-3까지 허용된다.

예제 입력 1

3 10
1 2 6
0 4 3
0 8 2

예제 출력 1

6.000000

예제 입력 2

5 15
0 4 3
1 5 5
1 6 6
0 9 2
0 10 3

예제 출력 2

8.500000

문제의 그림에서 X축이 굵은선으로 되어있는 부분은 TV 신호를 받을 수 없는 곳이다.

W3sicHJvYmxlbV9pZCI6Ijk2MzAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJUViBcdWMxYTFcdWMyZTBcdWFlMzAiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzJkY1x1YzdhNVx1Yzc0MCBcdWMwYzhcdWI4NWNcdWM2YjQgVFYgXHVjMWExXHVjMmUwIFx1YzJkY1x1YzJhNFx1ZDE1Y1x1Yzc0NCBcdWIzYzRcdWM3ODVcdWQ1NThcdWFlMzBcdWI4NWMgXHVkNTg4XHViMmU0LiBcdWIzYzRcdWMyZGNcdWIyOTQgXHVhZTM4XHVjNzc0XHVhYzAwIERcdWM3NzggXHVjMTIwXHViZDg0IFx1YzcwNFx1YzVkMCBcdWM1ZWNcdWI3ZWMgXHVhYzFjXHVjNzU4IFx1YmU0Y1x1YjUyOVx1Yzc3NCBcdWIxOTNcdWM1ZWNcdWM4MzggXHVjNzg4XHViMjk0IFx1ZDYxNVx1ZDBkY1x1Yzc3NFx1YjJlNC4gXHViZTRjXHViNTI5XHVjNzU4IFx1YjEwOFx1YmU0NFx1YjI5NCBcdWJiMzRcdWMyZGNcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1Yzc0NFx1YjljY1x1ZDA3YyBcdWM3OTFcdWIyZTQuIFx1Yzc3Y1x1YmQ4MCBcdWJlNGNcdWI1MjlcdWM3NTggXHVjNjI1XHVjMGMxXHVjNWQwXHViMjk0IFRWIFx1YzFhMVx1YzJlMFx1YWUzMCBcdWM3ODhcdWM3M2NcdWJhNzAsIFx1YWRmOCBcdWQwNmNcdWFlMzBcdWIzYzQgXHViYjM0XHVjMmRjXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlRWIFx1YzFhMVx1YzJlMFx1YWUzMFx1YjI5NCBUViBcdWMyZTBcdWQ2MzhcdWI5N2MgXHViYWE4XHViNGUwIFx1YmMyOVx1ZDVhNVx1YzczY1x1Yjg1YyBcdWM4MDRcdWMxYTFcdWQ1NWNcdWIyZTQuIFx1YzJlMFx1ZDYzOFx1YjI5NCBcdWM5YzFcdWMxMjBcdWM3M2NcdWI4NWMgXHVjODA0XHVjMWExXHViNDE4XHViYTcwLCBcdWJlNGNcdWI1MjlcdWM3NDQgXHVkMWI1XHVhY2ZjXHVkNTYwIFx1YzIxOCBcdWM1YzZcdWIyZTQuIFx1YjNjNFx1YzJkY1x1Yzc1OCBcdWM3N2NcdWJkODBcdWJkODRcdWM3NDAgXHVhZTMwXHVjODc0XHVjNWQwIFx1YzEyNFx1Y2U1OFx1YjQxYyBcdWMxYTFcdWMyZTBcdWFlMzBcdWI4NWMgVFYgXHVjMmUwXHVkNjM4XHViOTdjIFx1YzIxOFx1YzJlMFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC91cGxvYWQuYWNtaWNwYy5uZXRcLzY5ZmZiZThjLWNlMDQtNGFlYS1iNjNlLTlkMjg2MDYzMTBmYlwvLVwvcHJldmlld1wvXCIgc3R5bGU9XCJ3aWR0aDogNjI3cHg7IGhlaWdodDogMzIwcHg7XCIgXC8+PFwvcD5cclxuXHJcbjxwPlRWIFx1YzJlMFx1ZDYzOFx1Yjk3YyBcdWJjMWJcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWMxMjBcdWJkODRcdWM3NDQgXHVjYzNlXHVhY2UwIFx1YWRmOCBcdWFlMzhcdWM3NzRcdWI5N2MgXHVjZDljXHViODI1XHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YmU0Y1x1YjUyOVx1Yzc1OCBcdWMyMTggTiAoMSAmbGU7IE4gJmxlOyAzJm1pZGRvdDsxMDxzdXA+NTxcL3N1cD4pXHVhY2ZjIFx1YjNjNFx1YzJkY1x1Yzc1OCBcdWFlMzhcdWM3NzQgRCgxICZsZTsgRCAmbGU7IDEwPHN1cD45PFwvc3VwPilcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgTlx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgaVx1YmM4OFx1YzlmOCBcdWJlNGNcdWI1MjlcdWM3NTggXHVjODE1XHViY2Y0XHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBcdWMxMzggXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxvbD5cclxuXHQ8bGk+XHViZTRjXHViNTI5XHVjNzU4IFx1YzYyNVx1YzBjMVx1YzVkMCBcdWMxYTFcdWMyZTBcdWFlMzBcdWFjMDAgXHVjMTI0XHVjZTU4XHViNDFjIFx1YWNiZFx1YzZiMFx1YzVkMCBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YzgxNVx1YzIxOFx1YjI5NCAxXHVjNzc0XHVhY2UwLCBcdWMxMjRcdWNlNThcdWI0MThcdWM5YzAgXHVjNTRhXHVjNzQwIFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCAwXHVjNzc0XHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWI0NTAgXHViYzg4XHVjOWY4IFx1YzgxNVx1YzIxOFx1YjI5NCBcdWJlNGNcdWI1MjlcdWM3NzQgXHViM2M0XHVjMmRjXHVjNzU4IFx1YzY3Y1x1Y2FiZCBcdWIwNWRcdWM3M2NcdWI4NWNcdWJkODBcdWQxMzAgXHViNWE4XHVjNWI0XHVjOWM0IFx1YWM3MFx1YjlhYyBYPHN1Yj5pPFwvc3ViPiAoMCAmbGU7IFg8c3ViPmk8XC9zdWI+ICZsZTsgRCkgXHVjNzc0XHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWMxMzggXHViYzg4XHVjOWY4IFx1YzgxNVx1YzIxOFx1YjI5NCBcdWJlNGNcdWI1MjlcdWM3NTggXHViMTkyXHVjNzc0IEg8c3ViPmk8XC9zdWI+ICgxICZsZTsgSDxzdWI+aTxcL3N1Yj4gJmxlOyAxMDxzdXA+OTxcL3N1cD4pIFx1Yzc3NFx1YjJlNC48XC9saT5cclxuPFwvb2w+XHJcblxyXG48cD5cdWJlNGNcdWI1MjlcdWM3NDAgXHVjNjdjXHVjYWJkXHVjNzNjXHViODVjXHViZDgwXHVkMTMwIFx1YjVhOFx1YzViNFx1YzljNCBcdWFjNzBcdWI5YWNcdWFjMDAgXHVjOTlkXHVhYzAwXHVkNTU4XHViMjk0IFx1YzIxY1x1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjQ1MCBcdWJlNGNcdWI1MjlcdWM3NzQgXHVhYzE5XHVjNzQwIFx1YWNmM1x1YzVkMCBcdWM3ODhcdWIyOTQgXHVhY2JkXHVjNmIwXHViMjk0IFx1YzVjNlx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YWQ2Y1x1ZDU1YyBcdWM4MTVcdWIyZjVcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWM2MjRcdWNjMjhcdWIyOTQgXHVjZDVjXHViMzAwIDEwPHN1cD4tMzxcL3N1cD5cdWFlNGNcdWM5YzAgXHVkNWM4XHVjNmE5XHViNDFjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiIsInNhbXBsZV9leHBsYWluXzIiOiI8cD5cdWJiMzhcdWM4MWNcdWM3NTggXHVhZGY4XHViOWJjXHVjNWQwXHVjMTFjIFhcdWNkOTVcdWM3NzQgXHVhZDc1XHVjNzQwXHVjMTIwXHVjNzNjXHViODVjIFx1YjQxOFx1YzViNFx1Yzc4OFx1YjI5NCBcdWJkODBcdWJkODRcdWM3NDAgVFYgXHVjMmUwXHVkNjM4XHViOTdjIFx1YmMxYlx1Yzc0NCBcdWMyMTggXHVjNWM2XHViMjk0IFx1YWNmM1x1Yzc3NFx1YjJlNC48XC9wPlxyXG4ifSx7InByb2JsZW1faWQiOiI5NjMwIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiT0RBXHUwMTYwSUxKQVx1MDEwY0kiLCJkZXNjcmlwdGlvbiI6IjxwPlRoZSBtYXlvciBoYXMgZGVjaWRlZCB0aGF0IGl0IGlzIGhpZ2ggdGltZSB0byBpbXBsZW1lbnQgYSBuZXcgc3lzdGVtIG9mIHRlbGV2aXNpb24gdHJhbnNtaXR0ZXJzLiBUaGUgY2l0eSBjYW4gYmUgcmVwcmVzZW50ZWQgYXMgYSBzZWdtZW50IG9mIHRoZSBsZW5ndGggRCBvbiB3aGljaCB0aGVyZSBhcmUgYnVpbGRpbmdzIG9mIGRpZmZlcmVudCBoZWlnaHRzLiBUaGUgd2lkdGggb2YgYSBidWlsZGluZyBpcyBuZWdsaWdpYmxlLiBPbiB0b3Agb2Ygc29tZSBidWlsZGluZ3MsIHRlbGV2aXNpb24gdHJhbnNtaXR0ZXJzIGFyZSBzZXQsIHRoZWlyIGRpbWVuc2lvbnMgYXJlIGFsc28gbmVnbGlnaWJsZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGVsZXZpc2lvbiB0cmFuc21pdHRlcnMgZW1pdCBhIHRlbGV2aXNpb24gc2lnbmFsIGluIGFsbCBkaXJlY3Rpb25zIGFyb3VuZCB0aGVtLiBUaGUgc2lnbmFsIGlzIHNwcmVhZCB0aHJvdWdoIHNwYWNlIGluIHN0cmFpZ2h0IGxpbmVzIGFuZCBjYW5ub3QgcGFzcyB0aHJvdWdoIGJ1aWxkaW5ncy4gQSBjZXJ0YWluIHBvaW50IGluIHRoZSBjaXR5IGlzIGNvbnNpZGVyZWQgY292ZXJlZCBpZiBpdCBpcyByZWFjaGVkIGJ5IGEgc2lnbmFsIGZyb20gYW4gZXhpc3RpbmcgdHJhbnNtaXR0ZXIuJm5ic3A7PFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvY2l0eS5wbmdcIiBzdHlsZT1cImhlaWdodDozMzhweDsgd2lkdGg6NjU0cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+RmluZCB0aGUgc2VnbWVudCBvZiB0aGUgY2l0eSBjb3ZlcmVkIGJ5IHRlbGV2aXNpb24gc2lnbmFsIGFuZCBvdXRwdXQgaXRzIGxlbmd0aC4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIHRoZSBpbnRlZ2VyIE4gKDEgJmxlOyBOICZsZTsgMyZtaWRkb3Q7MTA8c3VwPjU8XC9zdXA+KSwgdGhlIG51bWJlciBvZiBidWlsZGluZ3MsIGFuZCB0aGUgaW50ZWdlciBEICgxICZsZTsgRCAmbGU7IDEwPHN1cD45PFwvc3VwPiksIHRoZSBjaXR5IGxlbmd0aC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+RWFjaCBvZiB0aGUgZm9sbG93aW5nIE4gbGluZXMgY29udGFpbnMgdGhyZWUgbnVtYmVycyB3aGljaCBkZXNjcmliZSB0aGUgaTxzdXA+dGg8XC9zdXA+IGJ1aWxkaW5nOiZuYnNwOzxcL3A+XHJcblxyXG48b2w+XHJcblx0PGxpPmEgbnVtYmVyIHdoaWNoIGRldGVybWluZXMgd2hldGhlciB0aGVyZSBpcyBhIHRyYW5zbWl0dGVyIG9uIHRvcCBvZiB0aGUgYnVpbGRpbmc6IDAgKG5vKSBvciAxICh5ZXMpJm5ic3A7PFwvbGk+XHJcblx0PGxpPmFuIGludGVnZXIgWDxzdWI+aTxcL3N1Yj4gKDAgJmxlOyBYPHN1Yj5pPFwvc3ViPiAmbGU7IEQpLCB0aGUgZGlzdGFuY2UgYmV0d2VlbiB0aGUgYnVpbGRpbmcgYW5kIHRoZSBsZWZ0IGVuZCBvZiB0aGUgY2l0eSZuYnNwOzxcL2xpPlxyXG5cdDxsaT5hbiBpbnRlZ2VyIEg8c3ViPmk8XC9zdWI+ICgxICZsZTsgSDxzdWI+aTxcL3N1Yj4gJmxlOyAxMDxzdXA+OTxcL3N1cD4pLCB0aGUgYnVpbGRpbmcgaGVpZ2h0Jm5ic3A7PFwvbGk+XHJcbjxcL29sPlxyXG5cclxuPHA+VGhlIGJ1aWxkaW5ncyBhcmUgc29ydGVkIGluIGFzY2VuZGluZyBvcmRlciBieSB0aGUgZGlzdGFuY2UgZnJvbSB0aGUgbGVmdCBlbmQgb2YgdGhlIGNpdHkuIE5vIHR3byBidWlsZGluZ3Mgd2lsbCBiZSBsb2NhdGVkIG9uIHRoZSBzYW1lIGRpc3RhbmNlIGZyb20gdGhlIGxlZnQgZW5kIG9mIHRoZSBjaXR5LiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBmaXJzdCBhbmQgb25seSBsaW5lIG9mIG91dHB1dCBtdXN0IGNvbnRhaW4gdGhlIHJlcXVpcmVkIGxlbmd0aCBmcm9tIHRoZSB0ZXh0LiZuYnNwOzxcL3A+XHJcblxyXG48cD5Ob3RlOiB0aGUgbWF4aW11bSBwZXJtaXNzaWJsZSBkZXZpYXRpb24gZnJvbSB0aGUgb2ZmaWNpYWwgc29sdXRpb24gaXMgMTA8c3VwPi0zPFwvc3VwPi4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiPHA+VGhpcyBleGFtcGxlIGNvcnJlc3BvbmRzIHRvIHRoZSBpbWFnZSBmcm9tIHRoZSB0ZXh0LiBUaGUgaW1hZ2UgZGVwaWN0cyB0aGUgY2l0eS4gVGhlIGJ1aWxkaW5ncyBhcmUgbWFya2VkIHdpdGggdmVydGljYWwgbGluZXMsIGFuZCB0aGUgdHJhbnNtaXR0ZXJzIHdpdGggY2lyY2xlcyBvbiB0aGUgdG9wcyBvZiB0aGUgYnVpbGRpbmdzLiBUaGUgYm9sZCBsaW5lcyBvbiB0aGUgeC1heGlzIHJlcHJlc2VudCB0aGUgc2VnbWVudCBvZiB0aGUgY2l0eSBub3QgY292ZXJlZCBieSB0ZWxldmlzaW9uIHNpZ25hbC48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2giLCJzYW1wbGVfZXhwbGFpbl8yIjoiPHA+VGhpcyBleGFtcGxlIGNvcnJlc3BvbmRzIHRvIHRoZSBpbWFnZSBmcm9tIHRoZSB0ZXh0LiBUaGUgaW1hZ2UgZGVwaWN0cyB0aGUgY2l0eS4gVGhlIGJ1aWxkaW5ncyBhcmUgbWFya2VkIHdpdGggdmVydGljYWwgbGluZXMsIGFuZCB0aGUgdHJhbnNtaXR0ZXJzIHdpdGggY2lyY2xlcyBvbiB0aGUgdG9wcyBvZiB0aGUgYnVpbGRpbmdzLiBUaGUgYm9sZCBsaW5lcyBvbiB0aGUgeC1heGlzIHJlcHJlc2VudCB0aGUgc2VnbWVudCBvZiB0aGUgY2l0eSBub3QgY292ZXJlZCBieSB0ZWxldmlzaW9uIHNpZ25hbC48XC9wPlxyXG4ifV0=

출처

Contest > Croatian Open Competition in Informatics > COCI 2013/2014 > Contest #3 6번