首页 > 代码库 > 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