题意:给一些带颜色的点,求一个最小的矩形,恰好包括一半的红色点,且不包括蓝色点。

题解:暴力,求个二维前缀和,用容斥原理更新一下。N很小所以我采用了离散优化,跑了个0ms。

之前没写过二维前缀和,加上离散写得也不是很熟练,所以搞了2个小时,好在是一发就过了。貌似有个坑,线不要特判,不然wa。

#include<cstdio>
#include<cmath>
#include<vector>
#include<map>
#include<set>
#include<algorithm>
#include<cstring> using namespace std; //#define local const int maxn = ;
int Red; int X[maxn],szx;
int Y[maxn],szy; int G[maxn][maxn];
int sumb[maxn][maxn];
int suma[maxn][maxn]; struct Poi
{
int x,y;
int tp;
int sx,sy;
bool operator < (const Poi & rhs) const {
return x < rhs.x || (x == rhs.x && y < rhs.y);
}
void input(){
scanf("%d%d%d",&x,&y,&tp);
if(!tp)Red++;
}
void GetDis(){
sx = lower_bound(X,X+szx,x)-X;
sy = lower_bound(Y,Y+szy,y)-Y;
G[sx][sy] = tp;
}
}P[maxn]; const int INF = 0x7fffffff;
int main()
{
#ifdef local
freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
#endif // local
int N;
int cas = ;
while(~scanf("%d",&N)&&N){
Red = ;
memset(G,-,sizeof(G));
int minx = INF, miny = INF;
for(int i = ; i < N; i++){
P[i].input();
minx = min(minx,P[i].x);
miny = min(miny,P[i].y);
//Y[i] = P[i].y;
}
X[] = minx-; Y[] = miny- ;
for(int i = ; i <= N; i++) {
X[i] = P[i-].x;
Y[i] = P[i-].y;
}
sort(X,X+N+);
sort(Y,Y+N+);
szy = unique(Y,Y+N+) - Y;
szx = unique(X,X+N+) - X; memset(suma,,sizeof(suma));
memset(sumb,,sizeof(sumb)); for(int i = ; i < N; i++) P[i].GetDis(); for(int i = ; i < szx; i++)
for(int j = ; j < szy; j++){
suma[i][j] = suma[i-][j]+suma[i][j-]-suma[i-][j-]+(G[i][j]==);
sumb[i][j] = sumb[i-][j]+sumb[i][j-]-sumb[i-][j-]+(G[i][j]==);
}
Red >>= ;
int area = INF;
for(int lx = ; lx < szx; lx++){
for(int rx = lx+; rx < szx; rx++){
for(int ly = ; ly <szy; ly++){
for(int ry = ly+; ry < szy; ry++){
if(suma[rx][ry]-suma[rx][ly]-suma[lx][ry]+suma[lx][ly]) continue;
if(Red == sumb[rx][ry]-sumb[rx][ly]-sumb[lx][ry]+sumb[lx][ly]){
area = min(area,(X[rx]-X[lx+])*(Y[ry]-Y[ly+]));
}
}
}
}
}
printf("Case %d: %d\n",++cas,area!=INF?area:-);
}
return ;
}

最新文章

  1. R语言:用简单的文本处理方法优化我们的读书体验
  2. Linux ftp访问控制配置,包括访问ftp权限和访问ftp目录权限
  3. vmware linux centos安装
  4. C++利用IO流对浮点数进行格式化控制输出
  5. Navicat premium工具常用快捷键
  6. Java编程中“为了性能”尽量要做到的一些地方
  7. HTTP头部解析
  8. Dictionary 的使用
  9. STL set的用法
  10. Linux - atexit()(注册终止)函数
  11. HTML5 客户端存储数据的两种方式
  12. SpringMVC源码情操陶冶-FreeMarker之web配置
  13. .NET MD5 加密
  14. js实现复选框的全选、全不选和反选
  15. .net core中使用Type.GetType()从字符串获取类型遇到的问题
  16. Configure Virtual Serial Port Driver (vspd)注册表
  17. php+sqlserver之如何操作sqlserver数据库
  18. casperjs get开头的几个dom操作使用
  19. DataTable学习笔记 - 01
  20. RTX——第13章 事件标志组

热门文章

  1. John 尼姆博弈
  2. HDU - 6114 2017百度之星初赛B Chess
  3. 如何使用jmeter连接数据库并提取数据库中的值作为参数,与响应信息中提取的值进行比较
  4. unity update优化
  5. 利用外部协议让chrome启动外部应用程序
  6. 理解SPI
  7. vim如何删除行首、行位空格、空格行
  8. enum StatCode
  9. 算法导论课后习题解答 第一部分 练习1.1-1-&gt;1.1-5
  10. 给Eclipse设置android的SDK位置时,出现这个:This Android SDK requires Andr...ate ADT to the latest