시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
10 초 512 MB 180 51 37 31.624%

문제

세계의 경제는 석유에 의존하고, 그것이 아직 남아있는 석유를 찾고 시추하는 방법을 개발하는 이유다. 정유회사의 수익은 얼마나 효율적으로 땅을 파야하는지에 달려있다. The International Crude Petroleum Consortium(ICPC)는 폭넓은 컴퓨터 시뮬레이션을 이용하여 얼마나 기름을 가능한 한 좋게 시추 할 수 있나 결정하려 한다.

새로 발견되는 석유는 하나로 뭉쳐있지 않고, 여러 갈래로 나뉘어져 있기 때문에 석유를 시추하는건 날이 가면 갈수록 어려워진다. ICPC는 현재 그림 G.1. 처럼 땅에 있는 석유 단층을 다루고 있다.

그림 G.1 : 땅에 뭍혀있는 석유 단층이다. 예제 입력 1과 같은 그림이다.

간단하게 분석하면, ICPC는 오직 석유 매장량과 평면만을 고려하여 지구 표면과 수평인 선분들을 그린다. ICPC는 하나의 시추 드릴에서 가장 최대의 석유를 뽑아내고 싶어한다. 석유는 지면으로부터 직선으로 시추되고, 드릴과 석유의 모든 교차점에서 시추가 가능하다. 심지어 석유층의 끝과 드릴이 닿아도 시추가 가능하다. 

한가지 예가 그림G.1과 같이 3개의 단층과 맞닿았다. 석유의 양은 좌우 넓이와 일치한다. 당신은 ICPC 가 하나의 시추드릴로 가장 많은 양의 석유를 시추할 수 있게 도와줄 수 있는가?

입력

입력의 첫 줄에는 석유층의 갯수인 정수 n (1 ≤ n ≤ 2 000) 이 입력된다.

다음 n개의 라인에는 각각의 석유 위치가 오게 되는데 각 줄은 3가지 정수 x0, x1 그리고  y 를 입력받게 된다. 석유위치는 (x0, y) 부터 (x1, y) 까지 위치하게 된다.

각 x0, x1 ,y는 |x0|, |x1| ≤ 10^6,  1 ≤ y ≤ 10^6 을 만족하며 석유는 서로 만나지 않으며 석유층의 끝끼리도 마주치지 않는다.

출력

하나의 시추드릴로 뽑을수 있는 최대 석유양을 출력하시오.

예제 입력 1

5
100 180 20
30 60 30
70 110 40
10 40 50
0 80 70

예제 출력 1

200

예제 입력 2

3
50 60 10
-42 -42 20
25 0 10

예제 출력 2

25
W3sicHJvYmxlbV9pZCI6IjEyNzcxIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjMTFkXHVjNzIwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWMxMzhcdWFjYzRcdWM3NTggXHVhY2JkXHVjODFjXHViMjk0IFx1YzExZFx1YzcyMFx1YzVkMCBcdWM3NThcdWM4NzRcdWQ1NThcdWFjZTAsIFx1YWRmOFx1YWM4M1x1Yzc3NCBcdWM1NDRcdWM5YzEgXHViMGE4XHVjNTQ0XHVjNzg4XHViMjk0IFx1YzExZFx1YzcyMFx1Yjk3YyZuYnNwO1x1Y2MzZVx1YWNlMCBcdWMyZGNcdWNkOTRcdWQ1NThcdWIyOTQgXHViYzI5XHViYzk1XHVjNzQ0IFx1YWMxY1x1YmMxY1x1ZDU1OFx1YjI5NCBcdWM3NzRcdWM3MjBcdWIyZTQuIFx1YzgxNVx1YzcyMFx1ZDY4Y1x1YzBhY1x1Yzc1OCBcdWMyMThcdWM3NzVcdWM3NDAmbmJzcDtcdWM1YmNcdWI5YzhcdWIwOTggXHVkNmE4XHVjNzI4XHVjODAxXHVjNzNjXHViODVjIFx1YjU0NVx1Yzc0NCBcdWQzMGNcdWM1N2NcdWQ1NThcdWIyOTRcdWM5YzBcdWM1ZDAgXHViMmVjXHViODI0XHVjNzg4XHViMmU0LiZuYnNwO1RoZSBJbnRlcm5hdGlvbmFsIENydWRlIFBldHJvbGV1bSBDb25zb3J0aXVtKElDUEMpXHViMjk0IFx1ZDNlZFx1YjExM1x1Yzc0MCZuYnNwO1x1Y2VmNFx1ZDRlOFx1ZDEzMCBcdWMyZGNcdWJiYWNcdWI4MDhcdWM3NzRcdWMxNThcdWM3NDQgXHVjNzc0XHVjNmE5XHVkNTU4XHVjNWVjIFx1YzViY1x1YjljOFx1YjA5OCBcdWFlMzBcdWI5ODRcdWM3NDQgXHVhYzAwXHViMmE1XHVkNTVjIFx1ZDU1YyBcdWM4OGJcdWFjOGMgXHVjMmRjXHVjZDk0IFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMDk4IFx1YWNiMFx1YzgxNVx1ZDU1OFx1YjgyNCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzBjOFx1Yjg1YyBcdWJjMWNcdWFjYWNcdWI0MThcdWIyOTQgXHVjMTFkXHVjNzIwXHViMjk0Jm5ic3A7XHVkNTU4XHViMDk4XHViODVjIFx1YmI0OVx1Y2NkMFx1Yzc4OFx1YzljMCBcdWM1NGFcdWFjZTAsIFx1YzVlY1x1YjdlYyBcdWFjMDhcdWI3OThcdWI4NWMgXHViMDk4XHViMjU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAgXHVjMTFkXHVjNzIwXHViOTdjJm5ic3A7XHVjMmRjXHVjZDk0XHVkNTU4XHViMjk0XHVhYzc0IFx1YjBhMFx1Yzc3NCBcdWFjMDBcdWJhNzQgXHVhYzA4XHVjMjE4XHViODVkIFx1YzViNFx1YjgyNFx1YzZjY1x1YzljNFx1YjJlNC4gSUNQQ1x1YjI5NCBcdWQ2MDRcdWM3YWMgXHVhZGY4XHViOWJjIEcuMS4gXHVjYzk4XHViN2ZjIFx1YjU0NVx1YzVkMCBcdWM3ODhcdWIyOTQgXHVjMTFkXHVjNzIwJm5ic3A7XHViMmU4XHVjZTM1XHVjNzQ0IFx1YjJlNFx1YjhlOFx1YWNlMCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgc3JjPVwiaHR0cHM6XC9cL29ubGluZWp1ZGdlaW1hZ2VzLnMzLWFwLW5vcnRoZWFzdC0xLmFtYXpvbmF3cy5jb21cL3Byb2JsZW1cLzEyNzcxXC8xLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjI2OXB4OyB0ZXh0LWFsaWduOmNlbnRlcjsgd2lkdGg6NTQ3cHhcIiBcLz48XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+XHVhZGY4XHViOWJjIEcuMSA6IFx1YjU0NVx1YzVkMCZuYnNwO1x1YmI0ZFx1ZDYwMFx1Yzc4OFx1YjI5NCBcdWMxMWRcdWM3MjAmbmJzcDtcdWIyZThcdWNlMzVcdWM3NzRcdWIyZTQuIFx1YzYwOFx1YzgxYyBcdWM3ODVcdWI4MjUgMVx1YWNmYyBcdWFjMTlcdWM3NDAgXHVhZGY4XHViOWJjXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDRcdWIyZThcdWQ1NThcdWFjOGMgXHViZDg0XHVjMTFkXHVkNTU4XHViYTc0LCBJQ1BDXHViMjk0IFx1YzYyNFx1YzljMSZuYnNwO1x1YzExZFx1YzcyMCBcdWI5ZTRcdWM3YTVcdWI3YzlcdWFjZmMmbmJzcDtcdWQzYzlcdWJhNzRcdWI5Y2NcdWM3NDQmbmJzcDtcdWFjZTBcdWI4MjRcdWQ1NThcdWM1ZWMmbmJzcDtcdWM5YzBcdWFkNmMgXHVkNDVjXHViYTc0XHVhY2ZjIFx1YzIxOFx1ZDNjOVx1Yzc3OCBcdWMxMjBcdWJkODRcdWI0ZTRcdWM3NDQgXHVhZGY4XHViOWIwXHViMmU0LiBJQ1BDXHViMjk0IFx1ZDU1OFx1YjA5OFx1Yzc1OCBcdWMyZGNcdWNkOTQgXHViNGRjXHViOWI0XHVjNWQwXHVjMTFjIFx1YWMwMFx1YzdhNSBcdWNkNWNcdWIzMDBcdWM3NTggXHVjMTFkXHVjNzIwXHViOTdjIFx1YmY1MVx1YzU0NFx1YjBiNFx1YWNlMCBcdWMyZjZcdWM1YjRcdWQ1NWNcdWIyZTQuIFx1YzExZFx1YzcyMFx1YjI5NCZuYnNwO1x1YzljMFx1YmE3NFx1YzczY1x1Yjg1Y1x1YmQ4MFx1ZDEzMCBcdWM5YzFcdWMxMjBcdWM3M2NcdWI4NWMgXHVjMmRjXHVjZDk0XHViNDE4XHVhY2UwLCBcdWI0ZGNcdWI5YjRcdWFjZmMgXHVjMTFkXHVjNzIwXHVjNzU4IFx1YmFhOFx1YjRlMCZuYnNwO1x1YWQ1MFx1Y2MyOFx1YzgxMFx1YzVkMFx1YzExYyBcdWMyZGNcdWNkOTRcdWFjMDAgXHVhYzAwXHViMmE1XHVkNTU4XHViMmU0LiBcdWMyZWNcdWM5YzBcdWM1YjQgXHVjMTFkXHVjNzIwXHVjZTM1XHVjNzU4IFx1YjA1ZFx1YWNmYyBcdWI0ZGNcdWI5YjRcdWM3NzQgXHViMmZmXHVjNTQ0XHViM2M0IFx1YzJkY1x1Y2Q5NFx1YWMwMCBcdWFjMDBcdWIyYTVcdWQ1NThcdWIyZTQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlx1ZDU1Y1x1YWMwMFx1YzljMCZuYnNwO1x1YzYwOFx1YWMwMCZuYnNwO1x1YWRmOFx1YjliY0cuMVx1YWNmYyBcdWFjMTlcdWM3NzQmbmJzcDszXHVhYzFjXHVjNzU4IFx1YjJlOFx1Y2UzNVx1YWNmYyBcdWI5ZGVcdWIyZmZcdWM1NThcdWIyZTQuIFx1YzExZFx1YzcyMFx1Yzc1OCBcdWM1OTFcdWM3NDAgXHVjODhjXHVjNmIwIFx1YjExM1x1Yzc3NFx1YzY0MCBcdWM3N2NcdWNlNThcdWQ1NWNcdWIyZTQuIFx1YjJmOVx1YzJlMFx1Yzc0MCBJQ1BDIFx1YWMwMCBcdWQ1NThcdWIwOThcdWM3NTggXHVjMmRjXHVjZDk0XHViNGRjXHViOWI0XHViODVjIFx1YWMwMFx1YzdhNSBcdWI5Y2VcdWM3NDAgXHVjNTkxXHVjNzU4IFx1YzExZFx1YzcyMFx1Yjk3YyBcdWMyZGNcdWNkOTRcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YWM4YyBcdWIzYzRcdWM2NDBcdWM5MDQmbmJzcDtcdWMyMTggXHVjNzg4XHViMjk0XHVhYzAwPzxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzU4IFx1Y2NhYiBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjMTFkXHVjNzIwXHVjZTM1XHVjNzU4IFx1YWMyZlx1YzIxOFx1Yzc3OCBcdWM4MTVcdWMyMTggbiZuYnNwOygxICZsZTsgbiAmbGU7IDIgMDAwKSBcdWM3NzQgXHVjNzg1XHViODI1XHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgblx1YWMxY1x1Yzc1OCBcdWI3N2NcdWM3NzhcdWM1ZDBcdWIyOTQgXHVhYzAxXHVhYzAxXHVjNzU4IFx1YzExZFx1YzcyMCBcdWM3MDRcdWNlNThcdWFjMDAgXHVjNjI0XHVhYzhjIFx1YjQxOFx1YjI5NFx1YjM3MCBcdWFjMDEgXHVjOTA0XHVjNzQwJm5ic3A7M1x1YWMwMFx1YzljMCBcdWM4MTVcdWMyMTgmbmJzcDt4MCwgeDEgXHVhZGY4XHViOWFjXHVhY2UwJm5ic3A7Jm5ic3A7eSBcdWI5N2MgXHVjNzg1XHViODI1XHViYzFiXHVhYzhjIFx1YjQxY1x1YjJlNC4gXHVjMTFkXHVjNzIwXHVjNzA0XHVjZTU4XHViMjk0Jm5ic3A7KHgwLCB5KSBcdWJkODBcdWQxMzAmbmJzcDsoeDEsIHkpIFx1YWU0Y1x1YzljMCBcdWM3MDRcdWNlNThcdWQ1NThcdWFjOGMmbmJzcDtcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMSB4MCwgeDEgLHlcdWIyOTQgfHgwfCwgfHgxfCAmbGU7IDEwXjYsJm5ic3A7Jm5ic3A7MSAmbGU7IHkgJmxlOyAxMF42IFx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWQ1NThcdWJhNzAgXHVjMTFkXHVjNzIwXHViMjk0IFx1YzExY1x1Yjg1YyBcdWI5Y2NcdWIwOThcdWM5YzAgXHVjNTRhXHVjNzNjXHViYTcwIFx1YzExZFx1YzcyMFx1Y2UzNVx1Yzc1OCBcdWIwNWRcdWIwN2NcdWI5YWNcdWIzYzQgXHViOWM4XHVjOGZjXHVjZTU4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWQ1NThcdWIwOThcdWM3NTggXHVjMmRjXHVjZDk0XHViNGRjXHViOWI0XHViODVjIFx1YmY1MVx1Yzc0NFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjZDVjXHViMzAwIFx1YzExZFx1YzcyMFx1YzU5MVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMTI3NzEiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJPaWwiLCJkZXNjcmlwdGlvbiI6IjxwPkEgbGFyZ2UgcGFydCBvZiB0aGUgd29ybGQgZWNvbm9teSBkZXBlbmRzIG9uIG9pbCwgd2hpY2ggaXMgd2h5IHJlc2VhcmNoIGludG8gbmV3IG1ldGhvZHMgZm9yIGZpbmRpbmcgYW5kIGV4dHJhY3Rpbmcgb2lsIGlzIHN0aWxsIGFjdGl2ZS4gUHJvZml0cyBvZiBvaWwgY29tcGFuaWVzIGRlcGVuZCBpbiBwYXJ0IG9uIGhvdyBlZmZpY2llbnRseSB0aGV5IGNhbiBkcmlsbCBmb3Igb2lsLiBUaGUgSW50ZXJuYXRpb25hbCBDcnVkZSBQZXRyb2xldW0gQ29uc29ydGl1bSAoSUNQQykgaG9wZXMgdGhhdCBleHRlbnNpdmUgY29tcHV0ZXIgc2ltdWxhdGlvbnMgd2lsbCBtYWtlIGl0IGVhc2llciB0byBkZXRlcm1pbmUgaG93IHRvIGRyaWxsIG9pbCB3ZWxscyBpbiB0aGUgYmVzdCBwb3NzaWJsZSB3YXkuPFwvcD5cclxuXHJcbjxwPkRyaWxsaW5nIG9pbCB3ZWxscyBvcHRpbWFsbHkgaXMgZ2V0dGluZyBoYXJkZXIgZWFjaCBkYXkgJm5kYXNoOyB0aGUgbmV3bHkgZGlzY292ZXJlZCBvaWwgZGVwb3NpdHMgb2Z0ZW4gZG8gbm90IGZvcm0gYSBzaW5nbGUgYm9keSwgYnV0IGFyZSBzcGxpdCBpbnRvIG1hbnkgcGFydHMuIFRoZSBJQ1BDIGlzIGN1cnJlbnRseSBjb25jZXJuZWQgd2l0aCBzdHJhdGlmaWVkIGRlcG9zaXRzLCBhcyBpbGx1c3RyYXRlZCBpbiBGaWd1cmUgRy4xLjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC9vbmxpbmVqdWRnZWltYWdlcy5zMy1hcC1ub3J0aGVhc3QtMS5hbWF6b25hd3MuY29tXC9wcm9ibGVtXC8xMjc3MVwvMS5wbmdcIiBzdHlsZT1cImhlaWdodDoyNjlweDsgd2lkdGg6NTQ3cHhcIiBcLz48XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+RmlndXJlIEcuMTogT2lsIGxheWVycyBidXJpZWQgaW4gdGhlIGVhcnRoLiBUaGlzIGZpZ3VyZSBjb3JyZXNwb25kcyB0byBTYW1wbGUgSW5wdXQgMS48XC9wPlxyXG5cclxuPHA+VG8gc2ltcGxpZnkgaXRzIGFuYWx5c2lzLCB0aGUgSUNQQyBjb25zaWRlcnMgb25seSB0aGUgMi1kaW1lbnNpb25hbCBjYXNlLCB3aGVyZSBvaWwgZGVwb3NpdHMgYXJlIG1vZGVsZWQgYXMgaG9yaXpvbnRhbCBsaW5lIHNlZ21lbnRzIHBhcmFsbGVsIHRvIHRoZSBlYXJ0aCZyc3F1bztzIHN1cmZhY2UuIFRoZSBJQ1BDIHdhbnRzIHRvIGtub3cgaG93IHRvIHBsYWNlIGEgc2luZ2xlIG9pbCB3ZWxsIHRvIGV4dHJhY3QgdGhlIG1heGltdW0gYW1vdW50IG9mIG9pbC4gVGhlIG9pbCB3ZWxsIGlzIGRyaWxsZWQgZnJvbSB0aGUgc3VyZmFjZSBhbG9uZyBhIHN0cmFpZ2h0IGxpbmUgYW5kIGNhbiBleHRyYWN0IG9pbCBmcm9tIGFsbCBkZXBvc2l0cyB0aGF0IGl0IGludGVyc2VjdHMgb24gaXRzIHdheSBkb3duLCBldmVuIGlmIHRoZSBpbnRlcnNlY3Rpb24gaXMgYXQgYW4gZW5kcG9pbnQgb2YgYSBkZXBvc2l0LiBPbmUgc3VjaCB3ZWxsIGlzIHNob3duIGFzIGEgZGFzaGVkIGxpbmUgaW4gRmlndXJlIEcuMSwgaGl0dGluZyB0aHJlZSBkZXBvc2l0cy4gSW4gdGhpcyBzaW1wbGUgbW9kZWwgdGhlIGFtb3VudCBvZiBvaWwgY29udGFpbmVkIGluIGEgZGVwb3NpdCBpcyBlcXVhbCB0byB0aGUgd2lkdGggb2YgdGhlIGRlcG9zaXQuIENhbiB5b3UgaGVscCB0aGUgSUNQQyBkZXRlcm1pbmUgdGhlIG1heGltdW0gYW1vdW50IG9mIG9pbCB0aGF0IGNhbiBiZSBleHRyYWN0ZWQgYnkgYSBzaW5nbGUgd2VsbD88XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIGEgc2luZ2xlIGludGVnZXIgbiAoMSAmbGU7IG4gJmxlOyAyIDAwMCksIHdoaWNoIGlzIHRoZSBudW1iZXIgb2Ygb2lsIGRlcG9zaXRzLiBUaGlzIGlzIGZvbGxvd2VkIGJ5IG4gbGluZXMsIGVhY2ggZGVzY3JpYmluZyBhIHNpbmdsZSBkZXBvc2l0LiBUaGVzZSBsaW5lcyBjb250YWluIHRocmVlIGludGVnZXJzIHg8c3ViPjA8XC9zdWI+LCB4PHN1Yj4xPFwvc3ViPiwgYW5kIHkgZ2l2aW5nIHRoZSBkZXBvc2l0JnJzcXVvO3MgcG9zaXRpb24gYXMgdGhlIGxpbmUgc2VnbWVudCB3aXRoIGVuZHBvaW50cyAoeDxzdWI+MDxcL3N1Yj4sIHkpIGFuZCAoeDxzdWI+MTxcL3N1Yj4sIHkpLiBUaGVzZSBudW1iZXJzIHNhdGlzZnkgfHg8c3ViPjA8XC9zdWI+fCwgfHg8c3ViPjE8XC9zdWI+fCAmbGU7IDEwPHN1cD42PFwvc3VwPiBhbmQgMSAmbGU7IHkgJmxlOyAxMDxzdXA+NjxcL3N1cD4uIE5vIHR3byBkZXBvc2l0cyB3aWxsIGludGVyc2VjdCwgbm90IGV2ZW4gYXQgYSBwb2ludC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5EaXNwbGF5IHRoZSBtYXhpbXVtIGFtb3VudCBvZiBvaWwgdGhhdCBjYW4gYmUgZXh0cmFjdGVkIGJ5IGEgc2luZ2xlIG9pbCB3ZWxsLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

ACM-ICPC > World Finals > 2016 World Finals G번