点击打开链接uva 1382
题意:给出平面上的n个点,找出一个矩形,使得边界上含有尽量多的点
思路:
1 很清楚,如果输入的n个点在同一行或者同一列的话那么ans = n。还有一种情况就是n个点的横坐标和纵坐标只有2种,那么这种情况ans = n。
2 对于这一题我们考虑的是枚举矩形的上下边界(纵坐标),然后利用其它的方法求左右边界,见下图
3 对于竖线i,我们用left[i]表示竖线左边位于上下边界的点数(不包括位于竖线i), on[i]表示竖线上位于上下边界之间的点数(和on2[i]的区别就是on[i]不统计位于上下边界的点数),这样给定左右边界i和j的话,矩形边界上的点数为left[j]+on2[j]+on[i]-left[i],当有边界j确定的时候,on[i]-left[i]要最大
4 那么我们枚举完上下边界后,我们利用O(n)的时间去求left[] , on[] , on2[],然后枚举有边界j,维护最大的on[i]-left[i]
代码:
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN = 110;
struct Node{
int x;
int y;
bool operator<(const Node& s)const{
return x < s.x;
}
};
Node node[MAXN];
int n , numy[MAXN];
int solve(){
sort(node , node+n);
sort(numy , numy+n);
int num = unique(numy , numy+n)-numy;
if(num <= 2)//如果纵坐标最多只有2个那么ans = n
return n;
//枚举上下界
int miny , maxy , ans;
int left[MAXN] , on[MAXN] , on2[MAXN];
ans = 0;
for(int i = 0 ; i < num ; i++){
for(int j = i+1 ; j < num ; j++){
miny = numy[i];
maxy = numy[j];
//求left , on , on2数组;
int k = -1;
memset(left , 0 , sizeof(left));
memset(on , 0 , sizeof(on));
memset(on2 , 0 , sizeof(on2));
for(int t = 0 ; t < n ; t++){
if(!t || node[t].x != node[t-1].x){
k++;
left[k] = k == 0 ? 0 : left[k-1]+on2[k-1]-on[k-1];
}
if(node[t].y > miny && node[t].y < maxy)
on[k]++;
if(node[t].y >= miny && node[t].y <= maxy)
on2[k]++;
}
if(k <= 1)//如果横坐标最多只有2个那么ans = n
return n;
int Max = 0;
for(int t = 0 ; t <= k ; t++){
ans = max(ans , left[t]+on2[t]+Max);
Max = max(Max , on[t]-left[t]);
}
}
}
return ans;
}
int main(){
int Case = 1;
while(scanf("%d" , &n) && n){
for(int i = 0 ; i < n ; i++){
scanf("%d%d" , &node[i].x , &node[i].y);
numy[i] = node[i].y;
}
printf("Case %d: %d\n" , Case++ , solve());
}
return 0;
}
分享到:
相关推荐
Distant galaxy
Mon-depot-distant
SF Distant Galaxy
entrepot-distant:Unentrepot遥远
DISTANT
Distant supervision 相关文献 Distant supervision 相关文献
Two problems arise when using distant su- pervision for relation extraction. First, in this method, an already existing knowl- edge base is heuristically aligned to texts, and the alignment results ...
Hopefully I will be able to attend your seminar in the not-too-distant future. Randall R. Hawley, Automation Technician, Eli Lilly & Co. The best computer book writing I have seen. Tom Holland
遥远的贝斯版权所有(c)2019-2021 该存储库包含distant-bes的代码,一个用于将构建结果注入实现服务的库。安装为了安装该库,请克隆此存储库并运行pip install distant-bes/ 。兼容性该库已经针对构建事件协议的...
Java 项目说明, 简单的例子能够说明如果列举项目类别
遥远的世界-宇宙-翻译遥远的世界宇宙的翻译#Installation:将lange 文件夹(例如DE)的内容复制到Distant Worlds Universe 文件夹(不是语言文件夹本身!)。 你应该先备份! #Credits 初始翻译来自 ! 欢迎所有帮助...
利用腔的输入和输出过程产生基于氮空缺中心的GHZ态纠缠,郑安寿,吕新友,本文提出了一种替代方案实现N量子比特的氮空位中心分布在不同的光子晶体纳腔的GHZ态纠缠,该方案的实现是基于光子的输入和输出过程�
Distant Supervised Relation Extraction with Cost-Sensitive Loss
代码片段: <h1 class='dilate'>Dilate ...<h1 class='distant-top'>Distant Top <h1 class='distant-front'>Distant Front <h1 class='diff1'>Diffused Light <h1 class='bevel'>Bevel</h1>
Deep Ranking Based Cost-sensitive Multi-label Learning for Distant Supervision Relation Extraction
噪音鲁棒的神经网络关系抽取模型,姜廷松,穗志方,关系抽取的目标是从文本中自动抽取实体间关系,远程监督能够自动标注训练数据,使得关系抽取可以面向大规模语料展开。远程监督面临�
Blocky distant lights 2.sut
遥远的阅读味道Projekt“远距离阅读品味” zum Kurs“数字人文科学”
WebRTC
Deep_Learning_for_Distant_Speech_Recognition Mirco Ravanelli