最大矩形面積

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);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;} }

轉載于:https://www.cnblogs.com/luoxiaoyi/p/9870238.html

總結

以上是生活随笔為你收集整理的Java练习 SDUT-2401最大矩形面积的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。