Đề bài

Time limit per test : 0.25 seconds

Memory limit per test : 256 megabytes

Sau hàng chục năm giảng dạy, GS.PVH đã sưu tập được rất nhiều bài tập triết học và giờ đây GS muốn tổng hợp và phân loại chúng. Các bài tập được in trong $n$ tờ giấy đặt trên bàn làm việc và GS.PVH muốn ấn các tờ giấy xuống dưới mặt bàn bằng một đim ghinh duy nhất (việc này là cần thiết nhằm tránh cho chúng bị xê dịch hoặc bị gió thổi bay).

Mặt bàn có thể coi như mặt phẳng với hệ tọa độ Descartes vuông góc $O$. Vị trí của các tờ giấy được xác định bởi hình chữ nhật đánh số từ $1$ tới $n$. Mỗi cạnh của mỗi hình chữ nhật song song hoặc vuông góc với đường phân giác của góc phần tư thứ nhất (góc $xOy$). Đim ghinh phải đặt ở vị trí có hoành độ và tung độ đều là số nguyên, đồng thời điểm đó phải thuộc miền trong của tất cả các hình chữ nhật (không tính đường biên).

Yêu cầu: Hãy giúp GS.PVH đếm số vị trí có thể đặt đim ghinh.

Input

Dòng một chứa số nguyên $n (1 ≤ n ≤ 10^5)$. $n$ dòng tiếp theo, mỗi dòng chứa tám số nguyên $x_A, y_A, x_B, y_B, x_C, y_C, x_D, y_D$ cách nhau bởi dấu cách là tọa độ bốn đỉnh $(x_A, y_A), (x_B, y_B), (x_C, y_C), (x_D, y_D)$ của một tờ giấy theo đúng thứ tự xác định hình chữ nhật tương ứng. Các tọa độ là số nguyên có giá trị tuyệt đối không quá $10^9$.

Output Ghi ra một số nguyên duy nhất là số vị trí có thể đặt đim ghinh.

Example

//Input
3
3 0 0 3 4 7 7 4
5 0 7 2 2 7 0 5
5 7 7 5 3 1 1 3

//Output
4

Nhận xét:

• Theo đề bài thì các hình chữ nhật chỉ có thể vuông góc với các hệ trục hoặc nghiêng 45 độ.
• Ta lấy ví dụ một hình chữ nhật của ví dụ bài cho:

• Ta có phương trình các đường thẳng chứa các cạnh của hình chữ nhật như sau:

  • Đường thẳng $CD$ có phương trình: $x + y = 11$;
  • Đường thẳng $CB$ có phương trình $x - y = -3$;
  • Đường thẳng $BA$ có phương trình $x + y = 3$;
  • Đường thẳng $AD$ có phương trình $x - y = 3$;

• Để một điểm nằm trong hình chữ nhật như trên thì chúng phải thoả mãn nằm "giữa" hai đường thẳng $AB$ và $CD$ và hai đường thẳng $BC$ và $AD$, về mặt toán học, gọi toạ độ điểm đó là $(x, y)$ thì $x, y$ phải thoả mãn các điều kiện sau:

$$\begin{cases} 3 < x + y < 11 \\ -3 < x - y < 3 \end{cases}$$

• Trong trường hợp hình chữ nhật vuông góc với các hệ trục toạ độ như sau:

• Thì ta có phương trình đường thẳng $AB$ là: $y = 1$; phương trình đường thẳng $BC$ là: $x = 7$; phương trình đường thẳng $CD$ là: $y = 6$; phương trình đường thẳng $DA$ là: $x = 3$;
• Để một điểm có toạ độ $(x, y)$ nằm trong hình chữ nhật trên, $x, y$ phải thoả mãn điều kiện:

$$\begin{cases} 3 < x < 7 \\ 1 < y < 6 \end{cases}$$

• Điều kiện này tương đương với :

$$\begin{cases} 4 < x + y < 13 \\ -3 < x - y < 1 \end{cases}$$

• Tóm lại, ta có công thức tổng quát: Để một điểm có toạ độ $(x; y)$ thuộc hình chữ nhật thì phải thoả mãn hai điều kiện:

$$\begin{cases} min(x_A + y_A, x_B + y_B, x_C + y_C, x_D + y_D) < x + y < max(x_A + y_A, x_B + y_B, x_C + y_C, x_D + y_D) \\ min(x_A - y_A, x_B - y_B, x_C - y_C, x_D - y_D) < x - y < max(x_A - y_A, x_B - y_B, x_C - y_C, x_D - y_D) \end{cases}$$

• Gọi :

$$\begin{cases} minsub[i] = min(x_A - y_A, x_B - y_B, x_C - y_C, x_D - y_D) \\ maxsub[i] = max(x_A - y_A, x_B - y_B, x_C - y_C, x_D - y_D) \\ minadd[i] = min(x_A + y_A, x_B + y_B, x_C + y_C, x_D + y_D) \\ maxadd[i] = max(x_A + y_A, x_B + y_B, x_C + y_C, x_D + y_D) \end{cases}$$

• Với $A, B, C, D$ là các điểm của hình chữ nhật thứ $i$. Như vậy, để một điểm có toạ độ $(x,y)$ nằm trong tất cả các hình chữ nhật thì phải thoả mãn hai điều kiện sau với $i$ chạy từ $1$ đến $n$, tức là $x + y$ và $x - y$ phải thuộc khoảng giao của tất cả điều kiện của các hình chữ nhật:

$$\begin{cases} max(minadd[i]) < x + y < min(maxadd[i]) \\ max(minsub[i]) < x - y < min(maxsub[i]) \end{cases}$$

• Đặt :

$$\begin{cases} S = x + y \\ T = x - y \end{cases}$$

• Ta nhận thấy $x = (S + T)/2$ và $y = (S - T)/2$, để $x$ và $y$ nguyên thì rõ ràng $S + T$ và $S - T$ đều phải chia hết cho $2$. Hay nói cách khác, $S$ và $T$ có cùng tính chẵn lẻ.

• Mặt khác, với mỗi cặp $(S, T)$ ta chỉ có thể tìm được duy nhất một cặp $(x, y)$ thoả mãn.

• Đặt :

$$\begin{cases} minsuball = max(minsub[i]) \\ maxsuball = min(maxsub[i]) \\ minaddall = max(minadd[i]) \\ maxaddall = min(maxadd[i]) \end{cases}$$

• Với $1 <= i <= n$ với ý nghĩa đây là giá trị của khoảng giao giữa các điều kiện của từng hình chữ nhật.

• Như vậy, bài toán trở về tìm số cặp $(S, T)$ có cùng tính chẵn lẻ sao cho:

$$\begin{cases} minaddall < S < maxaddall \\ minsuball < T < maxsuball \end{cases}$$

• Ta có kết quả của bài toán là:
  • Số số chẵn thuộc $(minsuball, maxsuball)$ nhân số số chẵn thuộc $(minaddall, maxaddall)$ + số số lẻ thuộc $(minsuball, maxsuball)$ nhân số số lẻ thuộc $(minaddall, maxaddall)$.

Hàm tính số số chẵn trong khoảng (a, b)

int demchan(int L, int R) {
    L++; R--; //Chuyển về [a + 1, b - 1]
    if (L%2 != 0) L++;// Nếu L không chia hết cho 2 thì tăng L đi 1
    if (R%2 != 0) R--;// Nếu R không chia hết cho 2 thì giảm R đi 1
    if (R < L) return 0;
    return (R - L)/2 + 1; //Công thức tính số phần tử của một cấp số cộng (u_n) với u1 = L, un = R và công sai là 2
}

Hàm tính số số lẻ trong khoảng (a ,b)

int demle(int L, int R) {
    L++; R--;
    if (L%2 == 0) L++;
    if (R%2 == 0) R--;
    if (R < L) return 0;
    return (R - L)/2 + 1;
}

Full code

#include <bits/stdc++.h>
#define MAX int(1000005) // Định nghĩa MAX bằng 10^6 + 5
#define INF int(2e9 + 10) // Định nghĩa dương vô cùng bằng 2*10^9 + 10
using namespace std;
int minsub[MAX], maxsub[MAX], minadd[MAX], maxadd[MAX];
int maxsuball, minsuball, maxaddall, minaddall;
int n;
void maximize(int &x, int y) { //Hàm tính max của x, y rồi truyền kết quả vào biến x
    x = max(x, y);
}
void minimize(int &x, int y) { // hàm tính min của x, y rồi truyền kết quả vào biến x
    x = min(x, y);
}
int demchan(int L, int R) { //Hàm tính số số chẵn
    L++; R--;
    if (L%2 != 0) L++;
    if (R%2 != 0) R--;
    if (R < L) return 0;
    return (R - L)/2 + 1;
}
int demle(int L, int R) { //hàm tính số số lẻ
    L++; R--;
    if (L%2 == 0) L++;
    if (R%2 == 0) R--;
    if (R < L) return 0;
    return (R - L)/2 + 1;
}
int main()
{
    //Lệnh tăng tốc độ đọc ghi của thuật toán
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    freopen("dimghinh.inp", "r", stdin); // Đọc input từ file dimghinh.inp
    freopen("dimghinh.out", "w", stdout); //In ra output ở file dimghinh.out

    memset(minsub, 0x3f, sizeof minsub); //Gán toàn bộ mảng minsub bằng một số dương nào đó rất lớn
    memset(maxsub, -0x3f, sizeof maxsub); //Gán toàn bộ mảng maxsub bằng một số âm nào đó rất nhỏ
    memset(minadd, 0x3f, sizeof minadd); // tương tự mảng minsub
    memset(maxadd, -0x3f, sizeof maxadd);// tương tự mảng maxsub

    cin >> n;
    for (int i = 1; i<=n; i++) {
        for (int j = 0; j<4; j++) { // Lặp 4 lần lấy dữ liệu của từng điểm của hình chữ nhật
            int x, y;
            cin >> x >> y;
            // Tính các khoảng của điều kiện của từng hình chữ nhật
            minimize(minsub[i], x - y); // minsub[i] = min(minsub[i], x - y)
            maximize(maxsub[i], x - y); // maxsub[i] = max(maxsub[i], x - y)
            minimize(minadd[i], x + y); // minadd[i] = min(minadd[i]; x + y)
            maximize(maxadd[i], x + y); // maxadd[i] = max(maxadd[i], x + y)
        }
    }

    maxsuball = INF; //Gán maxsuball bằng dương vô cùng
    minsuball = -INF; 
    maxaddall = INF;
    minaddall = -INF;

    // Tính khoảng giao của các điều kiện
    for (int i = 1; i<=n; i++)
    {
        minimize(maxsuball, maxsub[i]);
        maximize(minsuball, minsub[i]);
        minimize(maxaddall, maxadd[i]);
        maximize(minaddall, minadd[i]);
    }

    long long ll = 1;
    cout << ll*demchan(minaddall, maxaddall)*demchan(minsuball, maxsuball) + ll*demle(minaddall, maxaddall)*demle(minsuball, maxsuball);
    return 0;
}

Lưu ý

• Khi thực hiện nhân, kết quả có thể rất lớn, vì vậy ta thêm biến $ll = 1$ nhân vào nữa để tránh việc bị tràn số, dẫn đến kết quả sai, lỗi này cũng có thể khắc phục được bằng cách chuyển kiểu int của hàm tính số số chẵn và hàm tính số số lẻ thành kiểu long long để tránh bị tràn số.
• Lí do ta sử dụng lệnh $memset$ để gán cho mảng số rất lớn và số rất nhỏ là bởi sau này ta sử dụng lệnh tính max và min, nếu tính $min$ thì gán mảng thành số lớn, nếu tính $max$ thì gán mảng thành số bé, bởi nếu để nguyên theo mặc định là $0$ thì khi tính $min$ và $max$ kết quả rất có thể sẽ trở thành số $0$, gây sai sót, điều này cũng áp dụng với các biến như $minsuball, maxsuball, minaddall, maxaddall$.

Nguồn bài tập: Phạm Văn Hạnh.

Thiết kế giải thuật.