시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 2650 807 524 27.377%

문제

로고는 주로 교육용에 쓰이는 프로그래밍 언어이다. 로고의 가장 큰 특징은 거북이 로봇인데, 사용자는 이 거북이 로봇을 움직이는 명령을 입력해 화면에 도형을 그릴 수 있다.

거북이는 위치와 각도로 표현할 수 있다. 거북이는 입에 연필을 물고 있는데, 연필을 내리면 움직일 때 화면에 선을 그리고, 올리면 선을 그리지 않고 그냥 지나가기만 한다.

제일 처음에 거북이는 (0,0)에 있고, 거북이가 보고 있는 방향은 y축이 증가하는 방향이다. 또한 연필은 내리고 있다.

사용자는 다음과 같은 다섯가지 명령으로 거북이를 조정할 수 있다.

  1. FD x: 거북이를 x만큼 앞으로 전진
  2. LT a: 거북이를 반시계 방향으로 a도 만큼 회전
  3. RT a: 거북이를 시계 방향으로 a도 만큼 회전
  4. PU: 연필을 올린다
  5. PD: 연필을 내린다.

축에 평행한 직사각형 N개가 주어졌을 때, 이 직사각형을 그리는데 필요한 PU 명령의 최솟값을 구하는 프로그램을 작성하시오.

거북이는 같은 선을 여러 번 그릴 수 있지만, 문제에 주어진 직사각형 N개를 제외한 어떤 것도 그릴 수 없다. 거북이의 크기는 아주 작아서 좌표 평면의 한 점이라고 생각하면 된다. 직사각형의 변은 축에 평행하다.

입력

첫째 줄에 직사각형의 개수 N이 주어진다. (1 ≤ N ≤ 1000)

다음 N개의 줄에는 직사각형의 좌표 x1, y1, x2, y2가 주어진다. (−500 ≤ x1 < x2 ≤ 500), (−500 ≤ y1 < y2 ≤ 500) (x1, y1)는 직사각형의 한 꼭짓점 좌표이고, (x2, y2)는 그 점의 대각선 방향의 반대 꼭짓점의 좌표이다.

출력

N개의 직사각형을 그리는 필요한 PU명령의 최솟값을 출력한다.

예제 입력 1

5
1 1 4 4
3 3 6 6
4 4 5 5
5 0 8 3
6 1 7 2

예제 출력 1

2
W3sicHJvYmxlbV9pZCI6IjMxMDgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWI4NWNcdWFjZTAiLCJkZXNjcmlwdGlvbiI6IjxwPlx1Yjg1Y1x1YWNlMFx1YjI5NCBcdWM4ZmNcdWI4NWMgXHVhZDUwXHVjNzIxXHVjNmE5XHVjNWQwIFx1YzRmMFx1Yzc3NFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3OThcdWJjMGQgXHVjNWI4XHVjNWI0XHVjNzc0XHViMmU0LiBcdWI4NWNcdWFjZTBcdWM3NTggXHVhYzAwXHVjN2E1IFx1ZDA3MCBcdWQyYjlcdWM5ZDVcdWM3NDAgXHVhYzcwXHViZDgxXHVjNzc0IFx1Yjg1Y1x1YmQwN1x1Yzc3OFx1YjM3MCwgXHVjMGFjXHVjNmE5XHVjNzkwXHViMjk0IFx1Yzc3NCBcdWFjNzBcdWJkODFcdWM3NzQgXHViODVjXHViZDA3XHVjNzQ0IFx1YzZjMFx1YzljMVx1Yzc3NFx1YjI5NCBcdWJhODVcdWI4MzlcdWM3NDQgXHVjNzg1XHViODI1XHVkNTc0IFx1ZDY1NFx1YmE3NFx1YzVkMCBcdWIzYzRcdWQ2MTVcdWM3NDQgXHVhZGY4XHViOWI0IFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWM3MFx1YmQ4MVx1Yzc3NFx1YjI5NCBcdWM3MDRcdWNlNThcdWM2NDAgXHVhYzAxXHViM2M0XHViODVjIFx1ZDQ1Y1x1ZDYwNFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWFjNzBcdWJkODFcdWM3NzRcdWIyOTQgXHVjNzg1XHVjNWQwIFx1YzVmMFx1ZDU0NFx1Yzc0NCBcdWJiM2NcdWFjZTAgXHVjNzg4XHViMjk0XHViMzcwLCBcdWM1ZjBcdWQ1NDRcdWM3NDQgXHViMGI0XHViOWFjXHViYTc0IFx1YzZjMFx1YzljMVx1Yzc3YyBcdWI1NGMgXHVkNjU0XHViYTc0XHVjNWQwIFx1YzEyMFx1Yzc0NCBcdWFkZjhcdWI5YWNcdWFjZTAsIFx1YzYyY1x1YjlhY1x1YmE3NCBcdWMxMjBcdWM3NDQgXHVhZGY4XHViOWFjXHVjOWMwIFx1YzU0YVx1YWNlMCBcdWFkZjhcdWIwZTUgXHVjOWMwXHViMDk4XHVhYzAwXHVhZTMwXHViOWNjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjODFjXHVjNzdjIFx1Y2M5OFx1Yzc0Y1x1YzVkMCBcdWFjNzBcdWJkODFcdWM3NzRcdWIyOTQgKDAsMClcdWM1ZDAgXHVjNzg4XHVhY2UwLCBcdWFjNzBcdWJkODFcdWM3NzRcdWFjMDAgXHViY2Y0XHVhY2UwIFx1Yzc4OFx1YjI5NCBcdWJjMjlcdWQ1YTVcdWM3NDAgeVx1Y2Q5NVx1Yzc3NCBcdWM5OWRcdWFjMDBcdWQ1NThcdWIyOTQgXHViYzI5XHVkNWE1XHVjNzc0XHViMmU0LiBcdWI2MTBcdWQ1NWMgXHVjNWYwXHVkNTQ0XHVjNzQwIFx1YjBiNFx1YjlhY1x1YWNlMCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzBhY1x1YzZhOVx1Yzc5MFx1YjI5NCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzQwIFx1YjJlNFx1YzEyZlx1YWMwMFx1YzljMCBcdWJhODVcdWI4MzlcdWM3M2NcdWI4NWMgXHVhYzcwXHViZDgxXHVjNzc0XHViOTdjIFx1Yzg3MFx1YzgxNVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48b2w+XHJcblx0PGxpPkZEIHg6IFx1YWM3MFx1YmQ4MVx1Yzc3NFx1Yjk3YyB4XHViOWNjXHVkMDdjIFx1YzU1ZVx1YzczY1x1Yjg1YyBcdWM4MDRcdWM5YzQ8XC9saT5cclxuXHQ8bGk+TFQgYTogXHVhYzcwXHViZDgxXHVjNzc0XHViOTdjIFx1YmMxOFx1YzJkY1x1YWNjNCBcdWJjMjlcdWQ1YTVcdWM3M2NcdWI4NWMgYVx1YjNjNCBcdWI5Y2NcdWQwN2MgXHVkNjhjXHVjODA0PFwvbGk+XHJcblx0PGxpPlJUIGE6IFx1YWM3MFx1YmQ4MVx1Yzc3NFx1Yjk3YyBcdWMyZGNcdWFjYzQgXHViYzI5XHVkNWE1XHVjNzNjXHViODVjIGFcdWIzYzQgXHViOWNjXHVkMDdjIFx1ZDY4Y1x1YzgwNDxcL2xpPlxyXG5cdDxsaT5QVTogXHVjNWYwXHVkNTQ0XHVjNzQ0IFx1YzYyY1x1YjliMFx1YjJlNDxcL2xpPlxyXG5cdDxsaT5QRDogXHVjNWYwXHVkNTQ0XHVjNzQ0IFx1YjBiNFx1YjliMFx1YjJlNC48XC9saT5cclxuPFwvb2w+XHJcblxyXG48cD5cdWNkOTVcdWM1ZDAgXHVkM2M5XHVkNTg5XHVkNTVjIFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNSBOXHVhYzFjXHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1Yzc3NCBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NDQgXHVhZGY4XHViOWFjXHViMjk0XHViMzcwIFx1ZDU0NFx1YzY5NFx1ZDU1YyBQVSBcdWJhODVcdWI4MzlcdWM3NTggXHVjZDVjXHVjMTlmXHVhYzEyXHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcblxyXG48cD5cdWFjNzBcdWJkODFcdWM3NzRcdWIyOTQgXHVhYzE5XHVjNzQwIFx1YzEyMFx1Yzc0NCBcdWM1ZWNcdWI3ZWMgXHViYzg4IFx1YWRmOFx1YjliNCBcdWMyMTggXHVjNzg4XHVjOWMwXHViOWNjLCBcdWJiMzhcdWM4MWNcdWM1ZDAgXHVjOGZjXHVjNWI0XHVjOWM0IFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNSBOXHVhYzFjXHViOTdjIFx1YzgxY1x1YzY3OFx1ZDU1YyBcdWM1YjRcdWI1YTQgXHVhYzgzXHViM2M0IFx1YWRmOFx1YjliNCBcdWMyMTggXHVjNWM2XHViMmU0LiBcdWFjNzBcdWJkODFcdWM3NzRcdWM3NTggXHVkMDZjXHVhZTMwXHViMjk0IFx1YzU0NFx1YzhmYyBcdWM3OTFcdWM1NDRcdWMxMWMgXHVjODhjXHVkNDVjIFx1ZDNjOVx1YmE3NFx1Yzc1OCBcdWQ1NWMgXHVjODEwXHVjNzc0XHViNzdjXHVhY2UwIFx1YzBkZFx1YWMwMVx1ZDU1OFx1YmE3NCBcdWI0MWNcdWIyZTQuIFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc1OCBcdWJjYzBcdWM3NDAgXHVjZDk1XHVjNWQwIFx1ZDNjOVx1ZDU4OVx1ZDU1OFx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1XHVjNzU4IFx1YWMxY1x1YzIxOCBOXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBOICZsZTsgMTAwMCk8XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIE5cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc1OCBcdWM4OGNcdWQ0NWMgeDEsIHkxLCB4MiwgeTJcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoJm1pbnVzOzUwMCAmbGU7IHgxICZsdDsgeDIgJmxlOyA1MDApLCAoJm1pbnVzOzUwMCAmbGU7IHkxICZsdDsgeTIgJmxlOyA1MDApICh4MSwgeTEpXHViMjk0IFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc1OCBcdWQ1NWMgXHVhZjJkXHVjOWQzXHVjODEwIFx1Yzg4Y1x1ZDQ1Y1x1Yzc3NFx1YWNlMCwgKHgyLCB5MilcdWIyOTQgXHVhZGY4IFx1YzgxMFx1Yzc1OCBcdWIzMDBcdWFjMDFcdWMxMjAgXHViYzI5XHVkNWE1XHVjNzU4IFx1YmMxOFx1YjMwMCBcdWFmMmRcdWM5ZDNcdWM4MTBcdWM3NTggXHVjODhjXHVkNDVjXHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk5cdWFjMWNcdWM3NTggXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1XHVjNzQ0IFx1YWRmOFx1YjlhY1x1YjI5NCBcdWQ1NDRcdWM2OTRcdWQ1NWMgUFVcdWJhODVcdWI4MzlcdWM3NTggXHVjZDVjXHVjMTlmXHVhYzEyXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIzMTA4IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiTE9HTyIsImRlc2NyaXB0aW9uIjoiPHA+Q29tcGV0aXRpb24gdGFza3MgZm9yIHRoZSBwcm9ncmFtbWluZyBsYW5ndWFnZSBMT0dPIG9mdGVuIGludm9sdmUgZHJhd2luZyByZWN0YW5nbGVzIG9uIHRoZSBzY3JlZW4uIERyYXdpbmcgaW4gTE9HTyBpcyBkb25lIGJ5IG1vdmluZyBhIHR1cnRsZS1zaGFwZWQgY3Vyc29yLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgdHVydGxlIGlzIGRlZmluZWQgYnkgaXRzIHBvc2l0aW9uIGFuZCBhbmdsZS4gSXQgaG9sZHMgaW4gaXRzIG1vdXRoIGEgcGVuY2lsIHRoYXQgY2FuIGJlIHJhaXNlZCBvciBsb3dlcmVkLiBXaGVuIHRoZSBwZW5jaWwgaXMgbG93ZXJlZCwgbW92aW5nIHRoZSB0dXJ0bGUgY2F1c2VzIHRoZSBwZW5jaWwgdG8gbGVhdmUgYSB0cmFpbCBvbiB0aGUgc2NyZWVuLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgdHVydGxlIGlzIGluaXRpYWxseSBhdCBjb29yZGluYXRlcyAoMCwgMCkgZmFjaW5nIGluIHRoZSBkaXJlY3Rpb24gb2YgaW5jcmVhc2luZyB5IGNvb3JkaW5hdGVzLCBwZW5jaWwgbG93ZXJlZC4gV2UgY2FuIG1hbmlwdWxhdGUgdGhlIHR1cnRsZSB3aXRoIHRoZSBmb2xsb3dpbmcgc2V0IG9mIGNvbW1hbmRzOiZuYnNwOzxcL3A+XHJcblxyXG48b2w+XHJcblx0PGxpPkZEIHggJm5kYXNoOyBtb3ZlIHRoZSB0dXJ0bGUgeCB1bml0cyBmb3J3YXJkLiZuYnNwOzxcL2xpPlxyXG5cdDxsaT5MVCAmYWxwaGE7ICZuZGFzaDsgdHVybiB0aGUgdHVydGxlICZhbHBoYTsgZGVncmVlcyBjb3VudGVyLWNsb2Nrd2lzZS48XC9saT5cclxuXHQ8bGk+UlQgJmFscGhhOyAmbmRhc2g7IHR1cm4gdGhlIHR1cnRsZSAmYWxwaGE7IGRlZ3JlZXMgY2xvY2t3aXNlLiZuYnNwOzxcL2xpPlxyXG5cdDxsaT5QVSAmbmRhc2g7IHJhaXNlIHRoZSBwZW5jaWwuJm5ic3A7PFwvbGk+XHJcblx0PGxpPlBEICZuZGFzaDsgbG93ZXIgdGhlIHBlbmNpbC4mbmJzcDs8XC9saT5cclxuPFwvb2w+XHJcblxyXG48cD5Zb3VyIHByb2dyYW0gd2lsbCBiZSBnaXZlbiBhIHNldCBvZiByZWN0YW5nbGVzICh3aXRoIHNpZGVzIHBhcmFsbGVsIHRvIGNvb3JkaW5hdGUgYXhlcykgdGhhdCBuZWVkIHRvIGJlIGRyYXduIG9uIHRoZSBzY3JlZW4uIFRoZSB0dXJ0bGUgbWF5IGdvIG92ZXIgdGhlIHNhbWUgc2VnbWVudCB3aXRoIGl0cyBwZW5jaWwgbG93ZXJlZCBtdWx0aXBsZSB0aW1lcywgYnV0IGl0IGlzIG5vdCBhbGxvd2VkIHRvIGRyYXcgYW55dGhpbmcgb3RoZXIgdGhhbiB0aGUgZ2l2ZW4gcmVjdGFuZ2xlcy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHRoYXQgY2FsY3VsYXRlcyB0aGUgc21hbGxlc3QgbnVtYmVyIG9mIHRpbWVzIHRoZSBwZW5jaWwgbXVzdCBiZSByYWlzZWQgaW4gb3JkZXIgdG8gZHJhdyBhbGwgdGhlIHJlY3RhbmdsZXMuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBjb250YWlucyBhbiBpbnRlZ2VyIE4gKDEgJmxlOyBOICZsZTsgMTAwMCksIHRoZSBudW1iZXIgb2YgcmVjdGFuZ2xlcy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+RWFjaCBvZiB0aGUgZm9sbG93aW5nIE4gbGluZXMgY29udGFpbnMgZm9yIGludGVnZXJzIHgxLCB5MSwgeDIgYW5kIHkyICgmbWludXM7NTAwICZsZTsgeDEgJmx0OyB4MiAmbGU7IDUwMCksICgmbWludXM7NTAwICZsZTsgeTEgJmx0OyB5MiAmbGU7IDUwMCkgc2VwYXJhdGVkIGJ5IGEgc3BhY2UuIFRoZSBwb2ludHMgKHgxLCB5MSkgYW5kICh4MiwgeTIpIGFyZSBkaWFnb25hbGx5IG9wcG9zaXRlIGNvcm5lcnMgb2YgYSByZWN0YW5nbGUuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T3V0cHV0IHRoZSBzbWFsbGVzdCBudW1iZXIgb2YgdGltZXMgdGhlIHBlbmNpbCBtdXN0IGJlIHJhaXNlZCB0byBkcmF3IHRoZSByZWN0YW5nbGVzLiZuYnNwOzxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

Olympiad > Croatian Highschool Competitions in Informatics > 2009 > National Competition #1 - Juniors 2번

  • 문제를 번역한 사람: baekjoon
  • 잘못된 번역을 찾은 사람: devbelly