8616: Wall Builder I

内存限制:256 MB 时间限制:1 S
题面:传统 评测方式:Special Judge 上传者:
提交:0 通过:0

题目描述

As a wealthy man, NIO buys an empty house that can be viewed as a rectangle of length aaa and width bbb. As the builder employed by NIO, you need to divide the space of his house into several rooms.

NIO selects nnn points on the four borders of the house, and you should build the walls according to the following steps:
  1. Select a point on the border that has not been selected.
  2. Start building a wall vertical to the border from this point.
  3. Stop building when it meets the wall that has been built or another border of the house.
  4. End if all the points have been selected. Otherwise, go back to step 1.
After that, the space of the house will be divided into several rooms, the largest of which will serve as the living room. NIO wants his living room to be as large as possible. As you can decide the order of selection of the points, please tell him the maximum area of the living room. The thickness of the walls is negligible.

输入格式

The first line contains an integer TTT (1≤T≤1051 \le T \le 10^51T105), indicating the number of test cases.
The first line of each test case contains three integers n,a,bn,a,bn,a,b (1≤n≤1051 \le n \le 10^51n105, 1≤a,b≤1091 \le a,b \le 10^91a,b109), indicating the number of points on the border, the length of the house and the width of the house.
Each of the following nnn lines contains two integers x,yx,yx,y (0≤x≤a0 \le x \le a0xa, 0≤y≤b0 \le y \le b0yb), indicating the coordinate of the point. You can consider the house as a rectangle on the Cartesian coordinate system whose edges are parallel to the xxx or yyy axis, with one vertex at (0,0)(0,0)(0,0) and another at (a,b)(a,b)(a,b). For a point (x,y)(x,y)(x,y) on the border, it is guaranteed that one of the following conditions is met:
- x=0x=0x=0, 0<y<b0<y<b0<y<b
- x=ax=ax=a, 0<y<b0<y<b0<y<b
- 0<x<a0<x<a0<x<a, y=0y=0y=0
- 0<x<a0<x<a0<x<a, y=by=by=b
For any two different points (xi,yi)(x_i,y_i)(xi,yi) and (xj,yj)(x_j,y_j)(xj,yj), it is also guaranteed that:
- (xi,yi)≠(xj,yj)(x_i,y_i)\neq(x_j,y_j)(xi,yi)=(xj,yj).
- if ∣xi−xj∣=a|x_i-x_j|=axixj=a, then yi≠yjy_i \neq y_jyi=yj.
- if ∣yi−yj∣=b|y_i-y_j|=byiyj=b, then xi≠xjx_i \neq x_jxi=xj.
It is guaranteed that the sum of nnn over all test cases won't exceed 10510^5105.

输出格式

For each test case, output one integer indicating the maximum area of the living room in a single line.

输入样例 复制

2
4 4 4
0 1
1 0
4 3
3 4
4 4 4
0 1
0 3
1 0
3 0

输出样例 复制

9
8

数据范围与提示

A possible solution for the first test case in the sample:

A possible solution for the second test case in the sample:

分类标签