最大矩形面积_JAVA

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

Output

6

80

Hint

import java.util.*;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;}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;}}}}}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);elsedd = 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);elsedl = Math.max(dl, s[j].x);}}}return ans;} }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();} }

总结

以上是生活随笔为你收集整理的最大矩形面积_JAVA的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。