枚举指的是枚举矩阵的上下界,然后根据p0, p1, p2的关系去找出另外的中间2个点。然后需要记忆化一些地方防止重复减少时间复杂度。这应该是最关键的一步优化时间,指的就是代码中to数组。然后就是子矩阵的一个计算了,需要用二维前缀和预处理数据,然后判断的时候直接O(1)查询就好了。

#include<bits/stdc++.h>
using namespace std; const int inf = 0x3f3f3f3f;
const int maxn = 2e3 + ;
struct node{
int x, y;
node(){}
node(int x, int y) : x(x), y(y){}
}a[maxn], b[maxn], c[maxn], X[];
int p[], matdp[maxn][maxn], to[maxn][]; bool cmp1(const node &a, const node &b){
return a.x < b.x;
}
bool cmp2(const node &a, const node &b){
return a.y > b.y;
}
bool cmp3(const node &a, const node &b){
return a.y < b.y;
} int howmany(int x1, int y1, int x2, int y2){
return matdp[x2][y2] + matdp[x1 - ][y1 - ] - matdp[x1 - ][y2] - matdp[x2][y1 - ];
}
bool isOK(){
int x1 = inf, y1 = inf, x2 = , y2 = ;
for(int i = ; i < ; i ++){
x1 = min(x1, X[i].x); x2 = max(x2, X[i].x);
y1 = min(y1, X[i].y); y2 = max(y2, X[i].y);
for(int j = i + ; j < ; j ++)
if((p[j] - p[i]) * (X[j].y - X[i].y) <= ) return false;
}
return howmany(x1, y1, x2, y2) == ;
} int main(){
int T, n, m, k, x, y;scanf("%d",&T);
while(T --){
scanf("%d%d%d", &n, &m, &k);
scanf("%d%d%d%d", &p[], &p[], &p[], &p[]);
int big = , small = , ans = ;
(p[] > p[]) ? small ++ : big ++;
(p[] > p[]) ? small ++ : big ++;
memset(matdp, , sizeof(matdp));
for(int i = ; i <= k; i ++){
scanf("%d%d", &x, &y);matdp[x][y] = ;
a[i] = b[i] = c[i] = node(x, y);
}
for(int i = ; i <= n; i ++){
for(int j = ; j <= m; j ++)
matdp[i][j] += matdp[i][j - ];
for(int j = ; j <= m; j ++)
matdp[i][j] += matdp[i - ][j];
}
sort(a + , a + k + , cmp1);
sort(b + , b + k + , cmp2);
sort(c + , c + k + , cmp3);
for(int i = ; i <= k; i ++){
X[] = a[i];
for(int j = ; j <= k; j ++)
to[j][] = to[j][] = j == k ? : j + ;
for(int j = k; j > i; j --){
if(a[i].x == a[j].x) break;
if((p[] - p[]) * (a[j].y - a[i].y) <= ) continue;
X[] = a[j]; X[] = X[] = node(-, -);
int u = , v, bi = big, sm = small, t = ;
while(sm --){
for(v = u, u = to[u][]; u; to[v][] = to[u][], v = u, u = to[u][])
if(a[i].x < b[u].x && b[u].x < a[j].x && b[u].y < a[i].y){
X[t ++] = b[u];break;
}
}
u = ;
while(bi --){
for(v = u, u = to[u][]; u; to[v][] = to[u][], v = u, u = to[u][])
if(a[i].x < c[u].x && c[u].x < a[j].x && c[u].y > a[i].y){
X[t ++] = c[u];break;
}
}
if(t < || X[].x == X[].x) continue;
if(X[].x > X[].x) swap(X[], X[]);
if(isOK()) ans ++;
}
}
printf("%d\n",ans);
}
return ;
}

最新文章

  1. Asp.Net Razor中的Consistent Layout
  2. 利用IIS导出,导入快速部署 web站点
  3. 谷歌笔试题&mdash;&mdash;排序,只允许0和其他元素交换
  4. 337. House Robber III
  5. 网络解析之XML及JSON
  6. win10 uwp 判断文件存在
  7. C#学习笔记-工厂模式
  8. 【QT】Pycharm add QT Desinger
  9. Jmeter转换成中文模式
  10. [Docker] 容器持久化数据的首选机制 Volume
  11. rsync+inotify实现全网自动化数据备份-技术流ken
  12. Oracle表空间碎片整理SHRINK与MOVE
  13. Android中如何解决editText一进入activity就自动获取焦点的bug
  14. 【C++ Primer 第7章】定义抽象数据类型
  15. moment.js用法总结
  16. C# .NET 开发心得
  17. 求第N个回文数 模板
  18. .vimrc的配置
  19. 自定义type=&#39;file&#39;上传文件样式
  20. 访问虚拟机中的架设的Web服务器

热门文章

  1. 在Linux下用C语言实现短信收发
  2. GIt如何进行代码管理
  3. DMA驱动框架
  4. Why does the memory usage increase when I redeploy a web application?
  5. 使用natapp将本地服务映射到外网
  6. kafka2 简单介绍
  7. ABP中针对sql2008的数据库配置
  8. 1: 创建一个sap demo项目:
  9. github的使用,利用git shell命令行创建仓库并上传
  10. shell 中 标准输出和错误输出