Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

VOMOVREC - Di chuyển hình chữ nhật

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/vomovrec


Cho N hình chữ nhật trên mặt phẳng Oxy. Các hình chữ nhật này có toạ độ nguyên và có các cạnh song song với trục toạ độ. Ở mỗi lượt, các hình chữ nhật có thể đứng yên hoặc di chuyển theo 8 hướng:

  • sang trái 1 đơn vị
  • sang phải 1 đơn vị
  • lên trên 1 đơn vị
  • xuống dưới 1 đơn vị
  • sang trái và lên trên 1 đơn vị
  • sang trái và xuống dưới 1 đơn vị
  • sang phải và lên trên 1 đơn vị
  • sang phải và xuống dưới 1 đơn vị

Hãy xác định sau ít nhất bao nhiên lượt thì N hình chữ nhật ban đầu sẽ được di chuyển đến các vị trí mới sao cho phần diện tích giao nhau của tất cả N hình chữ nhật này lớn hơn hoặc bằng 1.

Dữ liệu vào

Dòng đầu tiên ghi số N là số lượng các hình chữ nhật.

Tiếp theo là N dòng, mỗi dòng ghi 4 số nguyên x1, y1, x2, y2 thể hiện hình chữ nhật có góc trái dưới là (x1, y1) góc phải trên là (x2, y2).

Dữ liệu ra

In ra số lượt di chuyển tối thiểu.

Giới hạn

Subtask 1 (30% số điểm)

  • 2 ≤ N ≤ 200
  • |tọa độ| ≤ 100
  • Chỉ gồm các hình vuông đơn vị với cạnh là 1

Subtask 2 (40% số điểm)

  • 200 < N ≤ 105
  • |toạ độ| ≤ 2 * 109
  • Chỉ gồm các hình vuông đơn vị với cạnh là 1

Subtask 3 (30% số điểm)

  • 200 < N ≤ 105
  • |tọa độ| ≤ 2 * 109

Ví dụ

Input:
3
0 0 1 1
0 0 2 3
2 3 4 5
Output:
2

Giải thích

 

Sau 2 lượt:

  • Hình 1: Di chuyển lên trên 1 đơn vị rồi sau đó di chuyển chéo lên phải 1 đơn vị.
  • Hình 2: Đứng yên.
  • Hình 3: Di chuyển chéo xuống trái 1 đơn vị.

Được gửi lên bởi:VOJ Team
Ngày:2015-12-25
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:C C++ 4.3.2 CPP CPP14 PAS-GPC PAS-FPC TEXT
Nguồn bài:VNOI Online 2016

hide comments
2016-07-27 16:37:12
mất 2 hit đầu vì test thử giới hạn :v 1e9->2e9->1e10 :))
2016-02-22 09:25:14 xin đừng quên tôi
Tham khảo thuận toán tại: http://yeulaptrinh.pw/63/spoj-vomovrec/
2016-02-01 08:47:18
THAM KHAO: http://codevnspoj.blogspot.com/
2015-12-30 10:40:58 ptt
bài này mình duyệt trâu chỉ được 30 điểm T.T
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.