挺好的一道题呢

O(n^2)或者O(wh)

 #include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<iostream> using namespace std; void setIO(const string& s) {
freopen((s + ".in").c_str(), "r", stdin);
freopen((s + ".out").c_str(), "w", stdout);
} template<typename Q> Q read(Q& x) {
static char c, f;
for(f = ; c = getchar(), !isdigit(c); ) if(c == '-') f = ;
for(x = ; isdigit(c); c = getchar()) x = x * + c - '';
return f && (x = -x), x;
}
template<typename Q> Q read() {
static Q x; return read(x);
} const int N = + ; struct Node {
int x, y;
Node(int x = , int y = ) : x(x), y(y) {}
}p[N]; bool cmpx(const Node& lhs, const Node& rhs) {
return lhs.x < rhs.x;
} bool cmpy(const Node& lhs, const Node& rhs) {
return lhs.y < rhs.y;
} int L, H, n;
int calc() {
int ans = ;
for(int i = ; i < n; i++) {
int U = H, D = ;
for(int j = i + ; j < n; j++) {
ans = max(ans, (p[j].x - p[i].x) * (U - D));
if(D <= p[j].y && p[j].y <= U) {
if(p[j].y > p[i].y) U = p[j].y;
else D = p[j].y;
}
if(U == D) break;
}
}
return ans;
} int main() {
#ifdef DEBUG
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif read(H), read(L), read(n);
for(int i = ; i < n; i++) {
int x = read<int>(), y = read<int>();
p[i] = Node(x, y);
}
p[n++] = Node(, );
p[n++] = Node(, H);
p[n++] = Node(L, );
p[n++] = Node(L, H); int ans = ;
sort(p, p + n, cmpy);
for(int i = ; i < n; i++) {
ans = max(ans, (p[i].y - p[i-].y) * L);
}
sort(p, p + n, cmpx);
ans = max(ans, calc());
for(int i = ; i < n; i++) p[i].x *= -;
reverse(p, p + n);
printf("%d\n", max(ans, calc())); return ;
}

最新文章

  1. mysql删除重复记录语句的方法
  2. eclipseMARS2.0使用可视化设计界面——配置window builder
  3. 分类指标准确率(Precision)和正确率(Accuracy)的区别
  4. Jmeter—6 CSV Data Set Config 通过文件导入数据
  5. Codeforces Round #241 (Div. 2)-&gt;B. Art Union
  6. Apache:如何利用.htaccess文件对PHP网站或文件进行伪静态处理
  7. 10个优秀的Objective-C和iOS开发在线视频教程
  8. springside springmvc 的一个SB问题
  9. jquery刷新iframe页面的方法
  10. 学习AJAX(二)
  11. REST Web Server,REST介绍
  12. SIGAR - System Information Gatherer And Reporter
  13. 如何使用ajax(jquery)
  14. curl讲解第一篇---入门和基本使用
  15. Vulkan Tutorial 22 Index buffer
  16. JDK源码分析(4)之 LinkedList 相关
  17. Python网络编程之Socket的简单实现
  18. ELK日志框架(1):安装Elasticsearch组建单服务器多节点集群
  19. [转帖] sparkdev 的 博客 systemd
  20. ThinkPHP 数据库操作之数据表模型和基础模型 ( Model )

热门文章

  1. HDU3591找零,背包
  2. 【elasticsearch】(2)centos7 超简单安装elasticsearch 的监控、测试的集群工具elasticsearch head
  3. Bootstrap_排版_表格
  4. RBM 与 DBN 学习笔记
  5. C语言学习笔记(一):数组传递时退化为指针
  6. 2016030102 - Ubuntu软件安装与删除相关命令
  7. 支付宝集成SDK 报错
  8. SpringMVC源码阅读(一)
  9. ARCI--做事情的重要方法论
  10. BZOJ 2754: [SCOI2012]喵星球上的点名