시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 1319 348 222 23.029%

문제

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

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

제일 처음에 거북이는 (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+XHJcblxyXG48cD5cdWFjNzBcdWJkODFcdWM3NzRcdWIyOTQgXHVhYzE5XHVjNzQwIFx1YzEyMFx1Yzc0NCBcdWM1ZWNcdWI3ZWMgXHViYzg4IFx1YWRmOFx1YjliNCBcdWMyMTggXHVjNzg4XHVjOWMwXHViOWNjLCBcdWJiMzhcdWM4MWNcdWM1ZDAgXHVjOGZjXHVjNWI0XHVjOWM0IFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNSBOXHVhYzFjXHViOTdjIFx1YzgxY1x1YzY3OFx1ZDU1YyBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NDQgXHVhZGY4XHViOWI0IFx1YzIxOCBcdWM1YzZcdWIyZTQuIFx1YWM3MFx1YmQ4MVx1Yzc3NFx1Yzc1OCBcdWQwNmNcdWFlMzBcdWIyOTQgXHVjNTQ0XHVjOGZjIFx1Yzc5MVx1YzU0NFx1YzExYyBcdWM4OGNcdWQ0NWMgXHVkM2M5XHViYTc0XHVjNzU4IFx1ZDU1YyBcdWM4MTBcdWM3NzRcdWI3N2NcdWFjZTAgXHVjMGRkXHVhYzAxXHVkNTU4XHViYTc0IFx1YjQxY1x1YjJlNC4gXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1XHVjNzU4IFx1YmNjMFx1Yzc0MCBcdWNkOTVcdWM1ZDAgXHVkM2M5XHVkNTg5XHVkNTU4XHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NTggXHVhYzFjXHVjMjE4IE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IE4gJmxlOyAxMDAwKTxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgTlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1XHVjNzU4IFx1Yzg4Y1x1ZDQ1YyB4MSwgeTEsIHgyLCB5Mlx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgmbWludXM7NTAwICZsZTsgeDEgJmx0OyB4MiAmbGU7IDUwMCksICgmbWludXM7NTAwICZsZTsgeTEgJmx0OyB5MiAmbGU7IDUwMCkgKHgxLCB5MSlcdWIyOTQgXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1XHVjNzU4IFx1ZDU1YyBcdWFmMmRcdWM5ZDNcdWM4MTAgXHVjODhjXHVkNDVjXHVjNzc0XHVhY2UwLCAoeDIsIHkyKVx1YjI5NCBcdWFkZjggXHVjODEwXHVjNzU4IFx1YjMwMFx1YWMwMVx1YzEyMCBcdWJjMjlcdWQ1YTVcdWM3NTggXHViYzE4XHViMzAwIFx1YWYyZFx1YzlkM1x1YzgxMFx1Yzc1OCBcdWM4OGNcdWQ0NWNcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Tlx1YWMxY1x1Yzc1OCBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NDQgXHVhZGY4XHViOWFjXHViMjk0IFx1ZDU0NFx1YzY5NFx1ZDU1YyBQVVx1YmE4NVx1YjgzOVx1Yzc1OCBcdWNkNWNcdWMxOWZcdWFjMTJcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjMxMDgiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJMT0dPIiwiZGVzY3JpcHRpb24iOiI8cD5Db21wZXRpdGlvbiB0YXNrcyBmb3IgdGhlIHByb2dyYW1taW5nIGxhbmd1YWdlIExPR08gb2Z0ZW4gaW52b2x2ZSBkcmF3aW5nIHJlY3RhbmdsZXMgb24gdGhlIHNjcmVlbi4gRHJhd2luZyBpbiBMT0dPIGlzIGRvbmUgYnkgbW92aW5nIGEgdHVydGxlLXNoYXBlZCBjdXJzb3IuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSB0dXJ0bGUgaXMgZGVmaW5lZCBieSBpdHMgcG9zaXRpb24gYW5kIGFuZ2xlLiBJdCBob2xkcyBpbiBpdHMgbW91dGggYSBwZW5jaWwgdGhhdCBjYW4gYmUgcmFpc2VkIG9yIGxvd2VyZWQuIFdoZW4gdGhlIHBlbmNpbCBpcyBsb3dlcmVkLCBtb3ZpbmcgdGhlIHR1cnRsZSBjYXVzZXMgdGhlIHBlbmNpbCB0byBsZWF2ZSBhIHRyYWlsIG9uIHRoZSBzY3JlZW4uJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSB0dXJ0bGUgaXMgaW5pdGlhbGx5IGF0IGNvb3JkaW5hdGVzICgwLCAwKSBmYWNpbmcgaW4gdGhlIGRpcmVjdGlvbiBvZiBpbmNyZWFzaW5nIHkgY29vcmRpbmF0ZXMsIHBlbmNpbCBsb3dlcmVkLiBXZSBjYW4gbWFuaXB1bGF0ZSB0aGUgdHVydGxlIHdpdGggdGhlIGZvbGxvd2luZyBzZXQgb2YgY29tbWFuZHM6Jm5ic3A7PFwvcD5cclxuXHJcbjxvbD5cclxuXHQ8bGk+RkQgeCAmbmRhc2g7IG1vdmUgdGhlIHR1cnRsZSB4IHVuaXRzIGZvcndhcmQuJm5ic3A7PFwvbGk+XHJcblx0PGxpPkxUICZhbHBoYTsgJm5kYXNoOyB0dXJuIHRoZSB0dXJ0bGUgJmFscGhhOyBkZWdyZWVzIGNvdW50ZXItY2xvY2t3aXNlLjxcL2xpPlxyXG5cdDxsaT5SVCAmYWxwaGE7ICZuZGFzaDsgdHVybiB0aGUgdHVydGxlICZhbHBoYTsgZGVncmVlcyBjbG9ja3dpc2UuJm5ic3A7PFwvbGk+XHJcblx0PGxpPlBVICZuZGFzaDsgcmFpc2UgdGhlIHBlbmNpbC4mbmJzcDs8XC9saT5cclxuXHQ8bGk+UEQgJm5kYXNoOyBsb3dlciB0aGUgcGVuY2lsLiZuYnNwOzxcL2xpPlxyXG48XC9vbD5cclxuXHJcbjxwPllvdXIgcHJvZ3JhbSB3aWxsIGJlIGdpdmVuIGEgc2V0IG9mIHJlY3RhbmdsZXMgKHdpdGggc2lkZXMgcGFyYWxsZWwgdG8gY29vcmRpbmF0ZSBheGVzKSB0aGF0IG5lZWQgdG8gYmUgZHJhd24gb24gdGhlIHNjcmVlbi4gVGhlIHR1cnRsZSBtYXkgZ28gb3ZlciB0aGUgc2FtZSBzZWdtZW50IHdpdGggaXRzIHBlbmNpbCBsb3dlcmVkIG11bHRpcGxlIHRpbWVzLCBidXQgaXQgaXMgbm90IGFsbG93ZWQgdG8gZHJhdyBhbnl0aGluZyBvdGhlciB0aGFuIHRoZSBnaXZlbiByZWN0YW5nbGVzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW0gdGhhdCBjYWxjdWxhdGVzIHRoZSBzbWFsbGVzdCBudW1iZXIgb2YgdGltZXMgdGhlIHBlbmNpbCBtdXN0IGJlIHJhaXNlZCBpbiBvcmRlciB0byBkcmF3IGFsbCB0aGUgcmVjdGFuZ2xlcy4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIGFuIGludGVnZXIgTiAoMSAmbGU7IE4gJmxlOyAxMDAwKSwgdGhlIG51bWJlciBvZiByZWN0YW5nbGVzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5FYWNoIG9mIHRoZSBmb2xsb3dpbmcgTiBsaW5lcyBjb250YWlucyBmb3IgaW50ZWdlcnMgeDEsIHkxLCB4MiBhbmQgeTIgKCZtaW51czs1MDAgJmxlOyB4MSAmbHQ7IHgyICZsZTsgNTAwKSwgKCZtaW51czs1MDAgJmxlOyB5MSAmbHQ7IHkyICZsZTsgNTAwKSBzZXBhcmF0ZWQgYnkgYSBzcGFjZS4gVGhlIHBvaW50cyAoeDEsIHkxKSBhbmQgKHgyLCB5MikgYXJlIGRpYWdvbmFsbHkgb3Bwb3NpdGUgY29ybmVycyBvZiBhIHJlY3RhbmdsZS4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgdGhlIHNtYWxsZXN0IG51bWJlciBvZiB0aW1lcyB0aGUgcGVuY2lsIG11c3QgYmUgcmFpc2VkIHRvIGRyYXcgdGhlIHJlY3RhbmdsZXMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==