首页 > 代码库 > The E-pang Palace
The E-pang Palace
·定位: 坑 + 模拟 + 暴力
·这种大模拟题好久没写了,,,不过还好,一个半小时,总算还是憋出来了。。。但可想而知,现场赛估计对这种题还是不敢动手,还是自己太菜 = =
·题意: 在所给的所有点中,找出两个不想交矩形,求两矩形最大覆盖面积。
坑: 注意 矩形嵌套矩形的情况:此时面积为大矩形的面积。
然后各种搞。。。
思路:
首先,枚举出所有可能存在的矩形情况;
其次,依次取两个矩形,判断其是否“相交”。
AC Code:
1 // 2 // main.cpp 3 // 20141104 4 // 5 // Created by songjs on 14-11-4. 6 // Copyright (c) 2014年 songjs. All rights reserved. 7 // 8 9 #include <iostream> 10 #include <stdio.h> 11 #include <algorithm> 12 #include <cstring> 13 #include <string.h> 14 #include <math.h> 15 #include <queue> 16 #include <stack> 17 #include <stdlib.h> 18 #include <map> 19 using namespace std; 20 #define LL long long 21 #define sf(a) scanf("%d",&(a)); 22 23 #define N 35 24 int n; 25 typedef struct LNode{ 26 int x,y; 27 }LNode; 28 LNode f[N]; 29 struct LNode2{ 30 LNode a,b; 31 }e[N]; 32 33 int search(int x,int y){ 34 int t1,t2;t1=t2=0; 35 for(int i=0;i<n;i++) 36 { 37 if(!t1 && f[i].x == f[x].x && f[i].y == f[y].y) {t1=1;continue;} 38 if(!t2 && f[i].x == f[y].x && f[i].y == f[x].y) {t2=1;continue;} 39 } 40 if(t1 && t2){ 41 if((f[x].x < f[y].x) && (f[x].y > f[y].y) ) 42 return 1; 43 } 44 return 0; 45 } 46 LNode p[2020]; 47 int jud3(LNode t,int k){ 48 //判断点是否在矩形e[k]内,不包含边界 49 if(t.x > e[k].a.x && t.x < e[k].b.x && t.y > e[k].b.y && t.y < e[k].a.y) return 1; 50 return 0; 51 } 52 int jud2(LNode t,int k){ 53 //判断点t是否在矩形e[k]内;包含边界 54 //包含时返回true; 55 if(t.x >= e[k].a.x && t.x <= e[k].b.x && t.y >= e[k].b.y && t.y <= e[k].a.y) return 1; 56 return 0; 57 } 58 59 int jud(int x,int y){ 60 //判断时注意坑点!! 可以一个大环嵌套一个小环!! 61 //返回值: 0代表有接触; 1代表无接触; 2代表无接触但是嵌套,x在内; 3代表无接触但是嵌套,y在内。 62 int flag=0;LNode t; 63 if(jud3(e[x].a,y)) flag++; //点在矩形中时(不包含边界),返回true 64 if(jud3(e[x].b,y)) flag++; 65 if(flag==2) return 2; //表示嵌套 66 flag=0; 67 if(jud3(e[y].a,x)) flag++; 68 if(jud3(e[y].b,x)) flag++; 69 if(flag==2) return 3; //表示嵌套 70 71 //下面考虑非嵌套的关系: 注意这里4个点都要进行判断!! 72 flag=0; 73 if(jud2(e[x].a,y)) flag++; 74 if(jud2(e[x].b,y)) flag++; 75 t.x = e[x].a.x; t.y = e[x].b.y; 76 if(jud2(t,y)) flag++; 77 t.x = e[x].b.x; t.y = e[x].a.y; 78 if(jud2(t,y)) flag++; 79 if(flag>0) return 0; //表示有接触 80 81 82 flag=0; 83 if(jud2(e[y].a,x)) flag++; 84 if(jud2(e[y].b,x)) flag++; 85 t.x = e[y].a.x; t.y = e[y].b.y; 86 if(jud2(t,x)) flag++; 87 t.x = e[y].b.x; t.y = e[y].a.y; 88 if(jud2(t,x)) flag++; 89 if(flag>0) return 0; 90 return 1; //表示无接触: 相离的状态 91 } 92 int cmd(LNode x,LNode y){ 93 if(x.y==y.y) return x.x < y.x; 94 return x.y > y.y; 95 } 96 int main() 97 { 98 while(scanf("%d",&n) && n){ 99 for(int i=0;i<n;i++){100 scanf("%d %d",&f[i].x,&f[i].y);101 }102 sort(f,f+n,cmd);//以y从大到小排序103 int k=0;104 for(int i=0;i<n;i++)105 for(int j=i+1;j<n;j++){106 if(search(i,j)){107 //有这样一个矩形,则加入数组e[]中。108 e[k].a = f[i];109 e[k++].b = f[j];110 }111 }112 //维护好了矩形的数组,再暴力枚举任意两个矩形,判断其是否相交。113 if(k<1) printf("imp\n");114 else{115 int num=-1;116 for(int i=0;i<k;i++){117 for(int j=i+1;j<k;j++){118 //判断两矩形是否相交119 int t = jud(i,j);120 if(t==0) continue;121 else if(t==1){122 //面积想加123 num = max(num , (e[i].a.y-e[i].b.y)*(e[i].b.x-e[i].a.x) + (e[j].a.y-e[j].b.y)*(e[j].b.x-e[j].a.x));124 }125 else{126 //选大的面积127 if(t==2){128 num = max(num,(e[j].a.y-e[j].b.y)*(e[j].b.x-e[j].a.x));129 }130 else {131 num = max(num,(e[i].a.y-e[i].b.y)*(e[i].b.x-e[i].a.x));132 }133 }134 135 }136 }137 if(num == -1) printf("imp\n");138 else printf("%d\n",num);139 }140 }141 return 0;142 }
The E-pang Palace
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。