InputThere are no more than 15 test case.
For each test case:
The first line is an integer N, meaning that there are N pillars left in E-pang Palace(4 <=N <= 30).
Then N lines follow. Each line contains two integers x and y (0 <= x,y <= 200), indicating a pillar‘s coordinate. No two pillars has the same coordinate.
The input ends by N = 0.OutputFor each test case, print the maximum total area of land Zhang Liang and Xiao He could get. If it was impossible for them to build two qualified fences, print "imp".Sample Input
8 0 0 1 0 0 1 1 1 0 2 1 2 0 3 1 3 8 0 0 2 0 0 2 2 2 1 2 3 2 1 3 3 3 0
Sample Output
2 imp
题目大意：给你一些点，从这些点中选择八个点组成两个矩形，求矩形面积的最大和是多少？两个矩形不能如下图形式：
解题思路：首先使用结构体存储矩形的点，然后对于这些点有两种排序方式。方式1：对x进行由小到大的排序(既上下排序)；方式2：对y进行由小到大的排序(既左右排序)，然后对于每个找到的矩形，下一个满足条件的矩形要么在它的右边；要么在他的上边。注意：如果“回”字形的矩形我们只要求出大矩形的面积和大矩形之外的矩形的面积只和就可以了。
1 #include <iostream> 2 #include <bits/stdc++.h> 3 4 using namespace std; 5 struct node 6 { 7 int x,y; 8 } a[50]; 9 int flag[2000][2000]; 10 int cmp2(const node &p,const node &q) 11 { 12 if(p.x!=q.x) 13 return p.x<q.x; 14 else 15 return p.y<q.y; 16 } 17 int cmp1(const node &p,const node &q) 18 { 19 if(p.y!=q.y) 20 return p.y<q.y; 21 else 22 return p.x<q.x; 23 } 24 int main() 25 { 26 int n; 27 while(~scanf("%d",&n)) 28 { 29 if(n==0) 30 break; 31 memset(flag,0,sizeof(flag)); 32 for(int i=0; i<n; i++) 33 { 34 scanf("%d%d",&a[i].x,&a[i].y); 35 flag[1000+a[i].x][1000+a[i].y]=1; 36 } 37 int maxx=0,cnt=0; 38 sort(a,a+n,cmp1); 39 for(int i=0; i<n; i++) 40 { 41 for(int j=i+1; j<n; j++) 42 { 43 if(a[j].x<=a[i].x||a[j].y<=a[i].y) 44 continue; 45 if(flag[a[i].x+1000][a[j].y+1000]==1&&flag[a[j].x+1000][a[i].y+1000]==1) 46 { 47 for(int u=i+1;u<j;u++) 48 { 49 for(int v=u+1;v<j;v++) 50 { 51 if((a[u].x>a[i].x&&a[v].x>a[u].x&&a[j].x>a[v].x)&&(a[u].y>a[i].y&&a[v].y>a[u].y&&a[j].y>a[v].y)&&(flag[a[u].x+1000][a[v].y+1000]==1&&flag[a[v].x+1000][a[u].y+1000]==1)) 52 { 53 cnt=1; 54 maxx=max(maxx,(a[j].x-a[i].x)*(a[j].y-a[i].y)); 55 } 56 } 57 } 58 int k; 59 for(k=0; k<n; k++) 60 if(a[k].y>a[j].y) 61 break; 62 for(int u=k; u<n; u++) 63 { 64 for(int v=u+1; v<n; v++) 65 { 66 if(a[v].x<=a[u].x||a[v].y<=a[u].y) 67 continue; 68 if(flag[a[u].x+1000][a[v].y+1000]==1&&flag[a[v].x+1000][a[u].y+1000]==1) 69 { 70 cnt=1; 71 maxx=max(maxx,(a[j].x-a[i].x)*(a[j].y-a[i].y)+(a[u].x-a[v].x)*(a[u].y-a[v].y)); 72 } 73 } 74 } 75 node eps[2]; 76 eps[0].x=a[i].x; 77 eps[0].y=a[i].y; 78 eps[1].x=a[j].x; 79 eps[1].y=a[j].y; 80 sort(a,a+n,cmp2); 81 for(k=0; k<n; k++) 82 if(a[k].x>eps[1].x) 83 break; 84 for(int u=k; u<n; u++) 85 { 86 for(int v=k; v<n; v++) 87 { 88 if(a[v].x<=a[u].x||a[v].y<=a[u].y) 89 continue; 90 if(flag[a[u].x+1000][a[v].y+1000]==1&&flag[a[v].x+1000][a[u].y+1000]==1) 91 { 92 cnt=1; 93 maxx=max(maxx,(eps[1].x-eps[0].x)*(eps[1].y-eps[0].y)+(a[u].x-a[v].x)*(a[u].y-a[v].y)); 94 } 95 } 96 } 97 } 98 } 99 sort(a,a+n,cmp1); 100 } 101 if(cnt==0) 102 { 103 printf("imp\n"); 104 } 105 else 106 { 107 printf("%d\n",maxx); 108 } 109 } 110 return 0; 111 }
原文：http://www.cnblogs.com/wang-ya-wei/p/7265389.html
