Codeforces Gym 100463D Evil DFS

题目链接:

题意:

给你一个坐标系，上面有n个点，要求找到一个矩形，使得能够框住一半的红点，不框进任何一个蓝点，求最小矩形面积

题解:

暴力枚举，注意，矩形面积可以为0

代码:

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 #define MS(a) memset(a,0,sizeof(a))
 5 #define MP make_pair
 6 #define PB push_back
 7 const int INF = 0x3f3f3f3f;
 8 const ll INFLL = 0x3f3f3f3f3f3f3f3fLL;
 9 inline ll read(){
10     ll x=0,f=1;char ch=getchar();
11     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
12     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
13     return x*f;
14 }
15 //////////////////////////////////////////////////////////////////////////
16 const int maxn = 1e5+10;
17 
18 int n,num1,num2,ans;
19 struct node{
20     int x,y;
21 }a[25],b[25];
22 
23 bool check(int xl,int xr,int yl,int yr){
24     for(int i=1; i<=num2; i++){
25         if((b[i].x>=xl&&b[i].x<=xr) && (b[i].y>=yl&&b[i].y<=yr))
26             return false;
27     }
28     return true;
29 }
30 
31 void dfs(int u, int pre, int xmin,int xmax,int ymin,int ymax){
32     if(u >= (num1)/2+1){
33         if(check(xmin,xmax,ymin,ymax))
34             ans = min(ans,(xmax-xmin)*(ymax-ymin));
35         return ;
36     }
37 
38     for(int i=pre+1; i<=num1; i++){
39         dfs(u+1, i, min(xmin,a[i].x),max(xmax,a[i].x),min(ymin,a[i].y),max(ymax,a[i].y)); // 前驱等于后继的时候 考虑只有一个点的情况 也就是矩形面积为零
40     }
41 }
42 
43 int main(){
44     int cas = 0;
45     while(scanf("%d",&n),n){
46         num1=num2=0;
47         cas++;
48         ans = INF;
49         for(int i=1; i<=n; i++){
50             int x=read(),y=read(),c=read();
51             if(c == 0)
52                 a[++num1].x=x,a[num1].y=y;
53             else
54                 b[++num2].x=x,b[num2].y=y;
55         }
56 
57         dfs(1,0,INF,-INF,INF,-INF);
58         if(ans != INF)
59             cout << "Case " << cas << ": " << ans << endl;
60         else
61             cout << "Case " << cas << ": " << -1 << endl;
62     }
63 
64     return 0;
65 }