首页 > 代码库 > The E-pang Palace
The E-pang Palace
题目：HDU5128 The E-pang Palace
解题思路：1.由于pillar的个数只有30个，故rectangular的个数最多15*14/2=105个，故可用暴力解法枚举rectangular的个数。
2.把每个点都作为rectangular左下角的点，进行枚举所有。
3.把找到的rectangular保存左下角和右上角x，y的坐标。
4.把找到的rectangular进行两两判断是否符合条件，找到最大的面积和。
5.注意2个rectangular嵌套的情况也是符合条件的，并且只算大的rectangular的面积。
代码如下：
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 5 using namespace std; 6 7 struct Pillar 8 { 9 int x;10 int y;11 }pillar[35];12 13 struct Rect14 {15 int x1;16 int y1;17 int x2;18 int y2;19 }rect[1000];20 21 int mp[210][210];22 23 int main()24 {25 int n;26 while (scanf("%d", &n) && n)27 {28 int l = 0;29 memset(mp, 0, sizeof(mp));30 int i, j, k;31 for (i = 0; i < n; i++)32 {33 scanf("%d%d", &pillar[i].x, &pillar[i].y);34 mp[pillar[i].x][pillar[i].y] = 1;35 }36 for (i = 0; i < n; i++)37 {38 for (j = pillar[i].x + 1; j <= 200; j++)39 {40 if (mp[j][pillar[i].y])41 {42 for (k = pillar[i].y + 1; k <= 200; k++)43 {44 if (mp[pillar[i].x][k] && mp[j][k])45 {46 rect[l].x1 = pillar[i].x;47 rect[l].y1 = pillar[i].y;48 rect[l].x2 = j;49 rect[l].y2 = k;50 l++;51 }52 }53 }54 }55 }56 int sum = 0;57 for (i = 0; i < l; i++)58 {59 for (j = i + 1; j < l; j++)60 {61 int s = 0;62 if ((rect[i].x1 - rect[j].x1) * (rect[i].x2 - rect[j].x2) < 0 && (rect[i].y1 - rect[j].y1) * (rect[i].y2 - rect[j].y2) < 0)63 {64 s = max((rect[i].y2 - rect[i].y1) * (rect[i].x2 - rect[i].x1), (rect[j].y2 - rect[j].y1) * (rect[j].x2 - rect[j].x1));65 }66 else if (rect[i].x1 > rect[j].x2 || rect[i].x2 < rect[j].x1 || rect[i].y1 > rect[j].y2 || rect[i].y2 < rect[j].y1)67 {68 s = (rect[i].y2 - rect[i].y1) * (rect[i].x2 - rect[i].x1) + (rect[j].y2 - rect[j].y1) * (rect[j].x2 - rect[j].x1);69 }70 sum = max(sum, s);71 }72 }73 if (sum)74 {75 printf("%d\n", sum);76 }77 else78 {79 printf("imp\n");80 }81 }82 83 84 return 0;85 }
AC如下：
The E-pang Palace
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。