hdu 5128 The E-pang Palace (有技巧的暴力）

this question can be find here

I ‘ve done this question twice and I didn’t make it the last time and I think I should write something about it
this question ask if we can find two rectangle at a map , have no shared edge or point , additionally any of their corners must be located at given point with the maximum area.
there is a trap , you can actually find two rectangle that one of them can contain the other one and it’s legal
and we can find four points that two of them is the diagonal point and check if they satisfy the condition

#include <bits/stdc++.h> #include <cstring> using namespace std; struct node {int x,y; } p[40]; int mp[210][201]; int check(int a,int b,int c,int d) {int lx1,lx2,ly1,ly2,rx1,rx2,ry1,ry2;lx1 = min(p[a].x,p[b].x);lx2 = min(p[c].x,p[d].x);ly1 = min(p[a].y,p[b].y);ly2 = min(p[c].y,p[d].y);rx1 = max(p[a].x,p[b].x);rx2 = max(p[c].x,p[d].x);ry1 = max(p[a].y,p[b].y);ry2 = max(p[c].y,p[d].y);int res;if(lx1==lx2&&ly1==ly2&&rx1==rx2&&ry1==ry2)return 0;if((ry1<ly2)||(ry2<ly1)||(lx1>rx2)||(lx2>rx1)){res=(rx1-lx1)*(ry1-ly1)+(rx2-lx2)*(ry2-ly2);return res;}if(lx2<lx1&&ly2<ly1&&rx1<rx2&&ry1<ry2){res=(rx2-lx2)*(ry2-ly2);return res;}if(lx1<lx2&&ly1<ly2&&rx2<rx1&&ry2<ry1){res=(rx1-lx1)*(ry1-ly1);return res;}elsereturn 0; } int main() {ios::sync_with_stdio(0);int n = 0;while(cin>>n){if(n == 0) break;int ans = 0;memset(mp,0,sizeof(mp));for(int i = 0; i<n; i++){cin>>p[i].x>>p[i].y;mp[p[i].x][p[i].y] = 1;}if(n<8){cout<<"imp"<<endl;continue;}for(int i = 0; i<n-1; i++){for(int j = i+1; j<n; j++){if( (p[i].x == p[j].x) || (p[i].y == p[j].y) ){continue;}else{int a = p[i].x;int b = p[i].y;int c = p[j].x;int d = p[j].y;if(mp[c][b]&& mp[a][d]){for(int k = 0; k<n-1; k++){if(k != i && k != j){for(int l = k+1; l<n; l++){if( l != i && l != j){if(p[k].x == p[l].x || p[k].y == p[l].y){continue;}else{if(mp[p[l].x][p[k].y] && mp[p[k].x][p[l].y]){ans = max(ans,check(i,j,k,l));}}}}}}}else{continue;}}}}if(ans == 0){cout<<"imp"<<endl;}else{cout<<ans<<endl;}} }

总结

以上是生活随笔为你收集整理的hdu 5128 The E-pang Palace (有技巧的暴力）的全部内容，希望文章能够帮你解决所遇到的问题。

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