這題雖然是暴力，但是我確實學到了。。。。每句對角線的高端做法。

參考博客：

https://blog.csdn.net/ck_boss/article/details/41720811

我自己的代碼：

解釋代碼中的一點，就是Judge里面的之所以要兩次相互判斷，是因為如果只判斷一次inside是無法判斷A包含B和B包含A的其中一種情況的，也就是說只能包含其中一種情況，會漏掉一種情況。

//C - The E-pang Palace #include<stdio.h> #include<string.h> #include<vector> #include<algorithm> using namespace std; #define MAXN 50 #define MAXN2 1010 #define INF 0x7f7f7f7fstruct Point {int x,y; }p[MAXN];struct Matrix {Point P[4];int Area; };vector<Matrix> M; int Map[MAXN2][MAXN2];bool Online(int i,int j)//判斷是否是對角線 {if(p[i].x==p[j].x||p[i].y==p[j].y)return true;return false; }void Make_Retan(int i,int j)//構造矩形 {Matrix m;int x1,y1;//對角線對應的剩下的兩個點int x2,y2;x1=max(p[i].x,p[j].x);y1=min(p[i].y,p[j].y);x2=min(p[i].x,p[j].x);y2=max(p[i].y,p[j].y);if(Map[x1][y1]&&Map[x2][y2]&&Map[x1][y2]&&Map[x2][y1])//剩余的兩個點在圖上存在{m.P[0].x=x2;m.P[0].y=y1;m.P[1].x=x1;m.P[1].y=y1;m.P[2].x=x1;m.P[2].y=y2;m.P[3].x=x2;m.P[3].y=y2;m.Area=(x1-x2)*(y2-y1);M.push_back(m);} }bool Inside(int &k,Point pp,Matrix X) {int l=X.P[0].x;int r=X.P[2].x;int up=X.P[2].y;int down=X.P[0].y;if((pp.x>l)&&(pp.x<r)&&(pp.y>down)&&(pp.y<up))//完全嵌套在里面，沒有點或邊相交k=1;if((pp.x>=l)&&(pp.x<=r)&&(pp.y>=down)&&(pp.y<=up))return true;return false; }int Judge(int i,int j) {int k1,k2,k3,k4;int res1,res2,res3,res4;Matrix A=M[i],B=M[j];k1=k2=k3=k4=0;res1=Inside(k1,A.P[0],B);res2=Inside(k2,A.P[1],B);res3=Inside(k3,A.P[2],B);res4=Inside(k4,A.P[3],B);if(res1||res2||res3||res4){if(k1&&k2&&k3&&k4)return B.Area;return -INF;}k1=k2=k3=k4=0;res1=Inside(k1,B.P[0],A);res2=Inside(k2,B.P[1],A);res3=Inside(k3,B.P[2],A);res4=Inside(k4,B.P[3],A);if(res1||res2||res3||res4){if(k1&&k2&&k3&&k4)return A.Area;return -INF;}//return A.Area+B.Area;//if(res1==false&&res2==false&&res3==false&&res4==false)return A.Area+B.Area;//return -INF; }int main() {int i,j;int N;int ans;while(scanf("%d",&N)&&N){memset(p,0,sizeof(p));memset(Map,0,sizeof(Map));for(i=0;i<N;i++){scanf("%d%d",&p[i].x,&p[i].y);Map[p[i].x][p[i].y]=1;}M.clear();for(i=0;i<N;i++)//枚舉對角線構造矩形{for(j=i+1;j<N;j++){if(Online(i,j))//判斷是否是對角線continue;Make_Retan(i,j);//構造矩形(但是不一定會成功，因為這條對角線對應的另外兩個點不一定存在)}}ans=-INF;for(i=0;i<M.size();i++)//枚舉任意兩個已經構造的矩形來求滿足條件的最大和{for(j=i+1;j<M.size();j++){ans=max(ans,Judge(i,j));//判斷兩個矩形是否滿足條件，如果滿足則算出面積和}}if(ans==-INF)printf("%s\n","imp");elseprintf("%d\n",ans);}return 0; }

?

總結

以上是生活随笔為你收集整理的HDOJ 5128 The E-pang Palace的全部內容，希望文章能夠幫你解決所遇到的問題。

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