Description
在一個矩形區(qū)域內(nèi)有很多點(diǎn)，每個點(diǎn)的坐標(biāo)都是整數(shù)。求一個矩形，使之內(nèi)部沒有點(diǎn)，且面積最大。所求矩形的邊與坐標(biāo)軸平行。
Input
一個整數(shù)t，表示測試組數(shù)。
整數(shù)l，w表示矩形橫向邊長和豎向邊長。
一個整數(shù)n，表示該矩形內(nèi)點(diǎn)的個數(shù)。
n個點(diǎn)的坐標(biāo)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();} }

總結(jié)

以上是生活随笔為你收集整理的最大矩形面积_JAVA的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。