最大矩形面积
Time Limit: 1000 ms Memory Limit: 65536 KiB
Problem Description
在一个矩形区域内有很多点，每个点的坐标都是整数。求一个矩形，使之内部没有点，且面积最大。所求矩形的边与坐标轴平行。
Input
一个整数t，表示测试组数。
整数l，w表示矩形横向边长和竖向边长。
一个整数n，表示该矩形内点的个数。
n个点的坐标x，y。
Output
最大面积。
Sample Input
2
2 3
0
10 10
4
1 1
9 1
1 9
9 9
Sample Output
6
80
题解：这道题是一道偏向思维的题目，先让点从左往右跑一边然后从上往下跑一边找出最大的矩形面积。注意边界的更新，需要让这个点再边界内部，一开始 我想的是根据面积最小的损失来更新这个点，结果后来意识到，比如一个点的x坐标7，此时的左右边界的值跟新为(0，6)，这个点就不再范围内了，这样就导致该点不再所求的矩形的边上，然而循环求的意义在于求与这个点有关的矩形的面积（点在矩形边上）。
import java.util.*;
public class Main {
public static void main(String []args)
{
Scanner cin = new Scanner(System.in);
int t,i,lr,ud;
node a = new node();
t = cin.nextInt();
while(t-->0)
{
a.l = cin.nextInt();
a.w = cin.nextInt();
a.n = cin.nextInt();
a.INIT();
//System.out.println(a.n);
for(i=2;i<a.n;i++)
{
a.s[i].x = cin.nextInt();
a.s[i].y = cin.nextInt();
}
lr = a.get_lr();
ud = a.get_ud();
System.out.println(Math.max(lr, ud));
}
cin.close();
}
}
class point
{
int x,y;
}
/*具体的解题代码*/
class node
{
int l,w,n;
point s[] = new point[1050];
/*初始化，让边界成为一个点（最大的矩形面积）*/
void INIT()
{
int i;
n = n + 2;
for(i=0;i<n;i++)
s[i] = new point();
s[0].x = 0;
s[0].y = 0;
s[1].x = l;
s[1].y = w;
}
/*根据x的大小对点进行排序*/
void sortlr()
{
int i,j;
point t = new point();
for(i=0;i<n;i++)
{
for(j=0;j<n-i-1;j++)
{
if(s[j].x>s[j+1].x)
{
t = s[j];
s[j] = s[j+1];
s[j+1] = t;
}
else if(s[j].x==s[j+1].x)
{
if(s[j].y>s[j+1].y)
{
t = s[j];
s[j] = s[j+1];
s[j+1] = t;
}
}
}
}
}
/*根据y的大小对点进行排序*/
void sortud()
{
int i,j;
point t = new point();
for(i=0;i<n;i++)
{
for(j=0;j<n-i-1;j++)
{
if(s[j].y>s[j+1].y)
{
t = s[j];
s[j] = s[j+1];
s[j+1] = t;
}
else if(s[j].y==s[j+1].y)
{
if(s[j].x>s[j+1].x)
{
t = s[j];
s[j] = s[j+1];
s[j+1] = t;
}
}
}
}
}
/*从左往右寻找最大的矩形面积*/
int get_lr()
{
int ans = 0,i,j,du,dd;
sortlr();
for(i=0;i<n-1;i++)
{
du = w;
dd = 0;
for(j=i+1;j<n;j++)
{
if(s[i].x!=s[j].x)
{
ans = Math.max(ans, (s[j].x-s[i].x)*(du-dd));
/*更新上下边界，注意让此时的点在边界范围内（即该点在矩形的边上）*/
if(s[j].y>s[i].y)
du = Math.min(du, s[j].y);
else
dd = Math.max(dd,s[j].y);
}
}
}
return ans;
}
/*从下往上找最大的矩形面积*/
int get_ud()
{
int ans = 0,i,j,dl,dr;
sortud();
for(i=0;i<n-1;i++)
{
dl = 0;
dr = l;
for(j=i+1;j<n;j++)
{
if(s[i].y!=s[j].y)
{
ans = Math.max(ans, (s[j].y-s[i].y)*(dr-dl));
/*更新上下边界*/
if(s[j].x>s[i].x)
dr = Math.min(dr, s[j].x);
else
dl = Math.max(dl, s[j].x);
}
}
}
return ans;
}
}