题目链接:uva 1312 - Cricket Field
题目大意:在w*h的图上有n个点,要求找出一个正方形面积最大,且没有点落在该正方形内部。
解题思路:枚举y坐标,每次遍历所有点,判断是否有点落在矩形内,有的话维护最优解,更新下线。
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int N = 105;
struct point {
int x, y;
}p[N];
int n, w, h, dy[N];
bool cmp(const point& a, const point& b) {
if (a.x != b.x) return a.x < b.x;
return a.y < b.y;
}
void init() {
scanf("%d%d%d", &n, &w, &h);
for (int i = 0; i < n; i++) {
scanf("%d%d", &p[i].x, &p[i].y);
dy[i] = p[i].y;
}
dy[n] = 0; dy[n+1] = h;
sort(dy, dy + n + 2);
sort(p, p + n, cmp);
}
void solve () {
int ansx, ansy, ans = 0;
int m = unique(dy, dy + n + 2) - dy;
for (int i = 0; i < m; i++) {
for (int j = i + 1; j < m; j++) {
int maxy = dy[j], miny = dy[i];
int hh = maxy - miny, ww = 0, tmp = 0;
for (int k = 0; k < n; k++) {
if (p[k].y <= miny || p[k].y >= maxy) continue;
ww = p[k].x - tmp;
if (ans < min(ww, hh)) {
ans = min(ww, hh);
ansx = tmp; ansy = miny;
}
tmp = p[k].x;
}
ww = w - tmp;
if (ans < min(ww, hh)) {
ans = min(ww, hh);
ansx = tmp; ansy = miny;
}
}
}
printf("%d %d %d\n", ansx, ansy, ans);
}
int main () {
int cas;
scanf("%d", &cas);
while (cas--) {
init();
solve();
if (cas) printf("\n");
}
return 0;
}
分享到:
相关推荐
英文版 DNS and BIND, 5th Edition - Cricket Liu & Paul Albitz
icc-cricket-world-cup-2019-数据集
A-Frame-AR-VR-cricket-pitch-:通过aframe.io实现VR和AR,并制作一个可在每个浏览器中运行的基于Web的应用程序
WCGS Cricket程序的初始例程和测试。 背景 WCGS体育部门在板球赛季需要一些帮助,并且需要一个计划来跟踪板球比赛的得分 任务 该任务要求您实现以下例程: over()-子程序来收集分数 innings()-子程序,用于...
Redux-Thunk-板球 使用创建应用 yarn create react-app . --template typescript yarn add reactstrap bootstrap @types/reactstrap node-sass yarn add redux react-redux @types/react-redux redux-thunk ...
score sheet for the use in cricket score card
ipl-t20-板球分析
Cricket Sports 相关的网页,Apache Nutch 框架被用于抓取以及将抓取的内容从抓取到托管在本地主机上的 Solr 框架,以便为抓取的网页建立索引,并创建用于实现页面排名和HITS 算法。 为什么要使用 Nutch? ● 生产...
板球机器人该机器人是使用discord.py api包装器模块以python编写的。 这个机器人是我制作的,因为我对板球比赛很感兴趣。 该机器人提供的游戏与现实生活中的板球游戏非常相似。... 注意:这不是漫游器的最终版本,更新...
现场板球比分 :cricket_game: 获取实时实时板球比分更新,而无需刷新页面。特征 :sparkles: 实时分数数据渐进式Web应用网站地图RSS订阅SEO和社交元标记模式标记规范网址离线支援移动响应式(使用Bulma CSS框架进行...
IPL_T20_Cricket_Analysis 此Almabetter Capstone项目(EDA)是由以下成员完成的培训项目: Pradip Solanki 阿缅·阿塔(Ameen Attar) 赫里西克·科亚西亚弗里迪·帕尔玛(Vridhi Parmar) 与团队合作解决这个项目...
用于获取数据的端点: 使用的框架和库: React JS 材质界面 阿克西奥斯 特征: 主页 - 您可以在这里快速浏览 20 篇体育文章。 搜索球员 - 您可以在其中输入球员的姓名、查看他们的统计数据并添加到您的团队中。...
以Cricket传感器为载体,根据射频和超声波信号的传输特性以及信标布局的特点设计了一种改进的通信机制,不但提高了传感器网络通信质量的而且也降低了传感器节点的能量消耗。并提出了一种与传感器工作机制相关且误差...
matlab标记部分代码板球活动检测 作者 阿肖克·库玛(Ashok Kumar) 贾夫什·加格(Javesh Garg) 该代码使用开源库以matlab,java和python编写。 所有代码分为三部分,一部分的代码捆绑在一起。...
Python- 在Python命令行界面上免费以个人或11人一组的形式对着11个机器人的团队玩板球! 有关游戏玩法的更多信息,请参见。关于这个游戏这是传统的板球游戏-用Python实现,并使用命令行界面进行游戏。...
预测板球比赛的结果 该项目旨在根据球队配置和球员之前的表现预测板球比赛的结果。 脚步 运行 scoreboards.py 以获取印度和任何其他国家/地区之间进行的比赛的记分牌网址。 包含 url 的列表将存储为 India_url.pkl ...
幻想板球背景此代码由 John Messenger 创建,作为 Helperby Cricket Club 的筹款活动运行。 如果您喜欢此代码,请随时向俱乐部捐款。 此外,请随时改进代码并将更改提交给我,以便可能并入存储库。文档除了应用程序...
最小化内部版本,文件名包含哈希值。 您的应用程序已准备好部署! 有关更多信息,请参阅有关的部分。 npm run eject 注意:这是一种单向操作。 一旦eject ,就回不去了! 如果您对构建工具和配置选择不满意,您...
板球统计数据模糊 从Cricinfo StatsGuru检索随机选择的统计信息,并每小时将其发为 。 作为部署在Heroku上的Play应用运行。 使用Heroku调度程序每小时进行一次推文。 去做 实施更多类型的统计数据:保龄球,球队...
活板球得分 LINK DESCIPTION 这是使用rick API的实时板球得分。 Tech REACT.JS和Material-UI。 使用钩子进行异步处理。 Deployment NETLIFY。