Vấn đề này được trình bày theo các bài trong kì thi OLP tin học sinh viên, giới hạn (subtask) được xếp ở cuối.

Nhằm mục đích gia tăng năng lực quốc phòng, khu quân sự \(NSHES\) xây dựng một vùng bẫy để chống lại các loại xe tăng bên địch. Vùng bẫy bao gồm các trụ điện từ có khả năng vô hiệu hóa bất kì cỗ xe chiến đấu nào mà bị vây quanh bởi một lớp phòng thủ - đa giác lồi tạo bởi các trụ điện. Trong mặt phẳng, một đường gấp khúc khép kín được gọi là đa giác, toàn bộ đa giác nằm cùng một phía của đường thẳng chứa cạnh bất kì của đa giác thì được gọi là đa giác lồi. Vị trí của các trụ điện được quy hoạch sao cho không có hai trụ nào được đặt quá gần nhau. Năng lực phòng thủ có thể được tăng cường thông qua việc sử dụng các lớp bổ sung bao quanh xe tăng, với điều kiện không lớp phòng thủ nào có giao điểm với các lớp phòng thủ còn lại.

\(NSHES\) tạo một bản đồ giả lập hai chiều gồm tọa độ của các trụ điện và vị trí của các xe tăng. Để thuận tiện cho việc tính toán, trên bản đồ mỗi xe tăng được coi như một hình chữ nhật và mỗi trụ điện được coi như một điểm. Bản đồ không có hai trụ nào trùng nhau nhưng các xe tăng có thể chồng lên nhau. Lớp phòng thủ bao quanh xe tăng nếu mọi điểm thuộc hình chữ nhật đều nằm trong hoặc nằm trên cạnh của đa giác lồi tương ứng với lớp phòng thủ đó. Ví dụ trong sơ đồ dưới đây, số lớp phòng thủ tối đa có thể bao quanh hai xe tăng lần lượt là \(1\) và \(2\).

Yêu cầu

Cho trước tọa độ của trụ điện, xác định tổng số lớp phòng thủ tối đa có thể sử dụng để vô hiệu hóa khi biết vị trí của các xe tăng.

Dữ liệu

Vào từ thiết bị nhập chuẩn với định dạng như sau:

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(k\), số lượng trụ điện và số lượng vị trí giả định của xe tăng quân địch.
• \(n\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(x\) và \(y\) \((-10^4 \le x, y \le 10^4)\) là tọa độ của các trụ điện.
• \(k\) dòng cuối cùng, mỗi dòng chứa các số nguyên \(x_1, y_1, x_2, y_2\) \((-10^4 \le x_1, y_1, x_2, y_2 \le 10^4, x_1< x_2, y_1 < y_2)\) mô tả vị trí của xe tăng theo hình chữ nhật:
  • \(x_1, y_1\) là tọa độ của góc dưới bên trái.
  • \(x_2, y_2\) là tọa độ của góc trên bên phải.

Kết quả

Đưa ra thiết bị xuất chuẩn một số nguyên duy nhất, tổng số lớp phòng thủ tối đa có thể vây quanh các xe tăng.

Ví dụ

Dữ liệu vào:

12 2
-4 2
-4 -2
0 2
0 -2
1 4
5 4
1 -4
5 -4
2 3
4 3
2 -3
4 -3
-3 -1 -1 1
3 0 4 1

Kết quả ra:

3

Giới hạn

Subtask \(1\) \((20\%\) số điểm\()\): \(3 \le n,k \le 6\).

Subtask \(2\) \((30\%\) số điểm\()\): \(3 \le n, k \le 2000\).

Subtask \(3\) \((50\%\) số điểm\()\): \(3 \le n\le 2000, 1 \le k \le 200000\).