/*
Time limit: 5000ms
Memory limit: 256mb

---------------------Copy the following code, complete it and submit---------------------
I, <Your Full Name>, am submitting the assignment for
an individual project.
I declare that the assignment here submitted is original except for
source material explicitly acknowledged, the piece of work, or a part
of the piece of work has not been submitted for more than one purpose
(i.e. to satisfy the requirements in two different courses) without
declaration. I also acknowledge that I am aware of University policy
and regulations on honesty in academic work, and of the disciplinary
guidelines and procedures applicable to breaches of such policy and
regulations, as contained in the University website
http://www.cuhk.edu.hk/policy/academichonesty/.
It is also understood that assignments without a properly signed
declaration by the student concerned will not be graded by the
teacher(s).
*/

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

#define MAX_LEN 1005
#define INT_MIN -2147483648

// Define the Set struct
struct Rectangle {
    int x1, y1, x2, y2;
};

// Function prototypes
// create a rectangle with given coordinates
struct Rectangle create_rectangle(int x1, int y1, int x2, int y2); 
// check if two rectangles overlap
int is_overlap(struct Rectangle r1, struct Rectangle r2);
// calculate the intersection of two rectangles
struct Rectangle intersection(struct Rectangle r1, struct Rectangle r2); 
// calculate the area of a rectangle
int area(struct Rectangle r);


/**
 * @brief create a rectangle with given coordinates
 * @param x1 x-coordinate of the left-bottom point
 * @param y1 y-coordinate of the left-bottom point
 * @param x2 x-coordinate of the right-top point
 * @param y2 y-coordinate of the right-top point
 * @return a Rectangle struct
 * @note x1 < x2, y1 < y2
 */
struct Rectangle create_rectangle(int x1, int y1, int x2, int y2) {
    struct Rectangle r;
    r.x1 = x1;
    r.y1 = y1;
    r.x2 = x2;
    r.y2 = y2;
    return r;
}


/**
 * @brief check if two rectangles overlap
 * @param r1 a Rectangle struct
 * @param r2 a Rectangle struct
 * @return 1 if overlap, 0 if not
 */
int is_overlap(struct Rectangle r1, struct Rectangle r2) {
    if(r1.x1 >= r2.x2 || r2.x1 >= r1.x2 || r1.y1 >= r2.y2 || r2.y1 >= r1.y2){
        return 0;
    }
    return 1;
}

/**
 * @brief calculate the intersection of two rectangles
 * @param r1 a Rectangle struct
 * @param r2 a Rectangle struct
 * @return a Rectangle struct representing the intersection
 * @note if the rectangles do not overlap, return a rectangle with area 0
 */
struct Rectangle intersection(struct Rectangle r1, struct Rectangle r2) {
    if (!is_overlap(r1, r2)) {
        return create_rectangle(0, 0, 0, 0);
    }
    struct Rectangle r;
    r.x1 = r1.x1 > r2.x1 ? r1.x1 : r2.x1;
    r.y1 = r1.y1 > r2.y1 ? r1.y1 : r2.y1;
    r.x2 = r1.x2 < r2.x2 ? r1.x2 : r2.x2;
    r.y2 = r1.y2 < r2.y2 ? r1.y2 : r2.y2;
    return r;
}


/**
 * @brief calculate the area of a rectangle
 * @param r a Rectangle struct
 * @return the area of the rectangle
 */
int area(struct Rectangle r) {
    return (r.x2 - r.x1) * (r.y2 - r.y1);
}


/**
 * @brief find the maximum intersection area of any two rectangles
 * @param x1 array of x-coordinates of the left-bottom points
 * @param y1 array of y-coordinates of the left-bottom points
 * @param x2 array of x-coordinates of the right-top points
 * @param y2 array of y-coordinates of the right-top points
 * @param n number of rectangles
 * @return the maximum intersection area
 * @note x1[i] < x2[i], y1[i] < y2[i] for all i
 */
int max_intersaction_area(int x1[], int y1[], int x2[], int y2[], int n) {
    // WRITE YOUR CODE HERE

}

// DO NOT MODIFY THE CODE BELOW
int main(void) {
    int n;
    scanf("%d", &n);
    
    int *x1 = (int *)malloc(n * sizeof(int));
    int *y1 = (int *)malloc(n * sizeof(int));
    int *x2 = (int *)malloc(n * sizeof(int));
    int *y2 = (int *)malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) {
        scanf("%d%d%d%d", &x1[i], &y1[i], &x2[i], &y2[i]);
    }

    int result = max_intersaction_area(x1, y1, x2, y2, n);
    printf("%d\n", result);

    free(x1);
    free(y1);
    free(x2);
    free(y2);
    return 0;
}


---------------------------------------End of Code---------------------------------------

## Maximum Rectangle Intersection

You need to use the predefined ADT `Rectangle` to solve the following problem:
- Given $n$ rectangles, find the maximum area of their intersection.

### Input
- First line contains an integer $n$ ($1 \leq n \leq 1000$), the number of rectangles.
- Each of the next $n$ lines contains four integers $x_1$, $y_1$, $x_2$, $y_2$ describing a rectangle.
- $(x_1, y_1)$ is the coordinate of the bottom-left corner.
- $(x_2, y_2)$ is the coordinate of the top-right corner.
- All coordinates are between $-10^4$ and $10^4$ inclusive.
- We guarantee that all input rectangles are valid, i.e., $x_1 < x_2$ and $y_1 < y_2$ for each rectangle.

### Output
A single number representing the maximum area of intersection between any pair of rectangles.
If no rectangles intersect, output $0$.

### Example
**Input**
```
3
0 0 2 2
1 1 3 3
2 0 4 2
```

**Output**
```
1
```

**Explanation**

In this example, rectangles $1$ and $2$ intersect in a $1\times 1$ square area (from $(1,1)$ to $(2,2)$). Rectangles $2$ and $3$ also intersect, but with the same area of $1$, whicle the rectangles $1$ and $3$ has no intersection.