题目链接
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=461&page=show_problem&problem=4058
题目大意:
在w*h的坐标上给n个点, 然后求一个最大的矩形,使得这个矩形内(不包括边界)没有点,注意边界上是可以有点的。
首先要把这些坐标进行离散化,离散话时要注意一点,如果有两个点原来坐标不是相邻的,但是离散化以后却变成相邻了,这时候要在它们之间加上一个点。
预处理后,枚举矩形上下界,然后再用O(n)的复杂度找出左右边界。
代码:
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cctype>
#include<cstring>
using namespace std;
const int MAXN = 120;
int n,w,h;
int row, col;
int d[MAXN];
int arr[MAXN][2];
int x[MAXN], y[MAXN];
int idx[10010], idy[10010];
int mat[MAXN][MAXN];
inline void input(){
x[0] = y[0] = 0;
row = col = 1;
// 输入并离散化
for(int i=0; i<n; ++i){
scanf("%d%d", &arr[i][0], &arr[i][1]);
x[row++] = arr[i][0];
y[col++] = arr[i][1];
}
x[row++] = w;
y[col++] = h;
sort(x, x+row);
sort(y, y+col);
row = unique(x, x+row) - x;
col = unique(y, y+col) - y;
int end = row;
for(int i=1; i<end; ++i)if(x[i] != x[i-1]+1){
x[row++] = x[i-1] + 1;
}
end = col;
for(int i=1; i<end; ++i)if(y[i] != y[i-1]+1){
y[col++] = y[i-1] + 1;
}
sort(x, x+row);
sort(y, y+col);
for(int i=0; i<row; ++i)
idx[x[i]] = i;
for(int i=0; i<col; ++i)
idy[y[i]] = i;
memset(mat, 0, sizeof(mat));
for(int i=0; i<n; ++i){
int a = idx[arr[i][0]];
int b = idy[arr[i][1]];
mat[a][b] = 1;
}
for(int i=0; i<row; ++i){
for(int j=0; j<col; ++j){
if(i==0) mat[i][j] += mat[i][j-1];
else if(j==0) mat[i][j] += mat[i-1][j];
else mat[i][j] += mat[i][j-1] + mat[i-1][j] - mat[i-1][j-1];
}
}
}
inline void solve(){
int maxLen=1, max_x=0, max_y=0;
int xx, yy;
for(int low=0; low<row-1; ++low){
for(int up=low+1; up<row; ++up){
memset(d, 0, sizeof(d));
for(int j=0; j<col; ++j){
int tmp;
if(j>0){
tmp = mat[up][j]-mat[low][j]
- (mat[up][j-1]-mat[low][j-1]);
}else{
tmp = mat[up][j]-mat[low][j];
}
if(tmp == 0){
d[j] = d[j-1] + 1;
int low_x = max(low, 0);
int low_y = max(j-d[j], 0);
int up_x = min(row-1, up+1);
int up_y = min(col-1, j+1);
int hh = x[up_x] - x[low_x];
int ww = y[up_y] - y[low_y];
int ll = min(hh, ww);
if(ll > maxLen){
maxLen = ll;
max_x = low_x;
max_y = low_y;
xx = up_x;
yy = up_y;
}
}
}
}}
printf("%d %d %d\n", x[max_x], y[max_y], maxLen);
}
int main(){
int nCase;
bool first=true;
scanf("%d", &nCase);
while(nCase--){
scanf("%d%d%d", &n, &w, &h);
first ? first=false : putchar('\n');
if(n==0){
printf("%d %d %d\n",0,0,min(w,h));
continue;
}
input();
solve();
}
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 ...
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 篇体育文章。 搜索球员 - 您可以在其中输入球员的姓名、查看他们的统计数据并添加到您的团队中。...
score sheet for the use in cricket score card
Python- 在Python命令行界面上免费以个人或11人一组的形式对着11个机器人的团队玩板球! 有关游戏玩法的更多信息,请参见。关于这个游戏这是传统的板球游戏-用Python实现,并使用命令行界面进行游戏。...
matlab标记部分代码板球活动检测 作者 阿肖克·库玛(Ashok Kumar) 贾夫什·加格(Javesh Garg) 该代码使用开源库以matlab,java和python编写。 所有代码分为三部分,一部分的代码捆绑在一起。...
以Cricket传感器为载体,根据射频和超声波信号的传输特性以及信标布局的特点设计了一种改进的通信机制,不但提高了传感器网络通信质量的而且也降低了传感器节点的能量消耗。并提出了一种与传感器工作机制相关且误差...
预测板球比赛的结果 该项目旨在根据球队配置和球员之前的表现预测板球比赛的结果。 脚步 运行 scoreboards.py 以获取印度和任何其他国家/地区之间进行的比赛的记分牌网址。 包含 url 的列表将存储为 India_url.pkl ...
板球统计数据模糊 从Cricinfo StatsGuru检索随机选择的统计信息,并每小时将其发为 。 作为部署在Heroku上的Play应用运行。 使用Heroku调度程序每小时进行一次推文。 去做 实施更多类型的统计数据:保龄球,球队...
幻想板球背景此代码由 John Messenger 创建,作为 Helperby Cricket Club 的筹款活动运行。 如果您喜欢此代码,请随时向俱乐部捐款。 此外,请随时改进代码并将更改提交给我,以便可能并入存储库。文档除了应用程序...
幻想板球 从幻想板球队中添加和删除球员的简单功能实现 创建 React 应用程序入门 这个项目是用引导的。 可用脚本 在项目目录中,可以运行: npm start 在开发模式下运行应用程序。 打开在浏览器中查看。...
活板球得分 LINK DESCIPTION 这是使用rick API的实时板球得分。 Tech REACT.JS和Material-UI。 使用钩子进行异步处理。 Deployment NETLIFY。