MYF

HDU 5128 The E-pang Palace

Posted on | In | | Visitors

题目链接

HDU 5128

题目类型：暴力

题目分析

题目大意

总共有n个柱子，给出n个柱子的坐标，让你从中选出8个柱子，形成两个矩形，矩形的四条边必须要和坐标轴平行，并且两个矩形的边不能相交或者相切。问，两个矩形所围成的面积最大多少

解析

写起来很费劲。因为坐标范围比较小，所以我干脆开了个200200的矩阵，来标记点。跑O(n\n)跑出所有矩形出来，每个矩形记录上下左右四个边界的坐标信息。然后在对所有的两个矩形的组合进行判断，判断对于矩形A和矩形B，A的四个顶点是否出现在B中，再判断B的四个顶点是否出现在A中。当然，还有一个特殊的情况，需要判断回字形，这种情况也是符合条件的。

为了写这道题，强忍着恶心重载了<和==，好吧，也算是学习了一下unique函数对于结构体去重的方法。

判断点在矩形内的时候写的实在不怎么优雅。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <string>
#include <vector>
#include <iomanip>
#include <bitset>
#include <cstring>
#include <iostream>
#include <iosfwd>
#include <deque>
#include <algorithm>
#define Memset(a,val) memset(a,val,sizeof(a))
#define PI acos(-1.0)
#define PB push_back
#define MP make_pair
#define rt(n)       (i == n ? '\n' : ' ')
#define hi         printf("Hi----------\n")
#define fre() freopen("data_in.txt","r",stdin); \
			  freopen("data_out.txt","w",stdout);
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
typedef pair<int,int> PII;
typedef long long ll;
const int mod=1000000007;
const int INF=0x3f3f3f3f;
const double eps=1e-8;
const int maxn=30+5;
int mp[205][205];
struct node{
	int x,y;
	node(){}
	node(int _x,int _y){
		x = _x, y = _y;
	}
}p[maxn];
struct block{
	int l,r,u,d;
	int area;
	block(){}
	block (node _a,node _b){
		l = min(_a.x, _b.x);
		r = max(_a.x, _b.x);
		d = min(_a.y, _b.y);
		u = max(_a.y, _b.y);
		area = (u-d)*(r-l);
	}
	void show(){
		printf("%d %d %d %d\n",l,r,d,u);
	}
	bool operator < (const block &a)const{
		if (l!=a.l) {
			return  l < a.l;
		}
		else if (r != a.r) {
			return r < a.r;
		}
		else if (u != a.u) {
			return u < a.u;
		}
		else {
			return d < a.d;
		}
	}
	bool operator == (const block &a)const{
		return l == a.l && r == a.r && d == a.d && u == a.u;
	}
}b[1005];
bool in(int x,int y, block a){
	return a.l<=x&&x<=a.r&&a.d<=y&&y<=a.u;
}
bool fuck(block a,block b){
	return a.l>b.l && a.r<b.r && a.u < b.u && a.d > b.d;
}
int main(){
	int n;
	while (scanf("%d",&n),n) {
		memset(mp, 0, sizeof(mp));
		for (int i = 1; i <= n ;i++) {
			scanf("%d%d",&p[i].x,&p[i].y);
			mp[p[i].x][p[i].y] = 1;
		}
		int cnt = 0;
		for (int i = 1; i <= n;i++) {
			for (int j = i+1;j <= n; j++) {
				if (p[i].x == p[j].x || p[i].y == p[j].y) continue;
				if (mp[p[i].x][p[j].y] && mp[p[j].x][p[i].y]) {
					b[++cnt] = block(p[i], p[j]);
				}
			}
		}
		int area= 0;
		sort(b+1, b+1+cnt);
		int bcnt = unique(b+1, b+1+cnt) - b - 1;
		
		for (int i = 1; i<=bcnt;i++) {
			int l = b[i].l, r = b[i].r, u = b[i].u, d = b[i].d;
			for (int j = i+1; j <= bcnt; j++) {
				if (in(b[i].l, b[i].u, b[j]) == false && in(b[i].r, b[i].u, b[j]) == false && in(b[i].l, b[i].d, b[j]) == false && in(b[i].r, b[i].d, b[j]) == false && in(b[j].l, b[j].u, b[i]) == false && in(b[j].r, b[j].u, b[i]) == false && in(b[j].l, b[j].d, b[i]) == false && in(b[j].r, b[j].d, b[i]) == false) {
					area = max(area, b[i].area + b[j].area);
				}
				if (fuck(b[i], b[j])) {
					area = max(area, b[j].area);
				}
				if (fuck(b[j], b[i])) {
					area = max(area, b[i].area);
				}
			}
		}
	
		if (area == 0) 
			printf("imp\n");
		else 
			cout<<area<<"\n";
	}
}