首页 技术 正文
技术 2022年11月23日
0 收藏 926 点赞 3,081 浏览 2780 个字

  一开始还以为对于每根竖线,只要与过了任意一点的横线相交都可以呢,这样枚举两条线就要O(n^2),结果发现自己想多了。。。

  其实是每个点画根竖线和横线就好,对于相同竖线统计(一直不包含线上点)右上左下总点数的最小值,最后不同竖线求一个最大值。对于每条等于这个最小值最大化的竖线都找一个右下与左上的最大值,排序输出即可。注意这儿排序后需要去重

  思想倒是不难,主要就是麻烦。只需要分别离散化x轴,y轴的点,然后枚举每个点找到四个方向的其他总点数,这儿用树状数组可以简单解决。但是注意空间问题不能开二维,开一维排序x轴,再左右扫一遍,一边计算一边添加点即可,注意x y轴线上的点要减去。先扫一边找到最小值最大化的值与每条竖线包含哪些点,再扫一遍找到等于那个值的竖线中的最大右下左上和

代码写得很麻烦

#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<vector>
#include<string>
#include<cstdio>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define eps 1E-8
/*注意可能会有输出-0.000*/
#define Sgn(x) (x<-eps? -1 :x<eps? 0:1)//x为两个浮点数差的比较,注意返回整型
#define Cvs(x) (x > 0.0 ? x+eps : x-eps)//浮点数转化
#define zero(x) (((x)>0?(x):-(x))<eps)//判断是否等于0
#define mul(a,b) (a<<b)
#define dir(a,b) (a>>b)
typedef long long ll;
typedef unsigned long long ull;
const int Inf=<<;
const double Pi=acos(-1.0);
const int Max=;
int bit[Max];
struct node
{
int xx1,yy1;
int lup,rup,ldo,rdo;
} poi[Max];
int n;
bool cmp1(struct node p1,struct node p2)
{
if(p1.xx1==p2.xx1)
return p1.yy1<p2.yy1;
return p1.xx1<p2.xx1;
}
bool cmp2(struct node p1,struct node p2)
{
return p1.yy1<p2.yy1;
}
int lowbit(int x)
{
return x&(-x);
}
void Add(int y)
{
while(y<=n)
{
bit[y]++;
y+=lowbit(y);
}
return;
}
int Sum(int y)
{
if(!y)
return ;
int sum=;
while(y>)
{
sum+=bit[y];
y-=lowbit(y);
}
return sum;
}
void Dtz()//离散化
{
sort(poi,poi+n,cmp2);
int m=;
poi[n].yy1=Inf;
for(int i=; i<n; i++)
{
if(poi[i].yy1!=poi[i+].yy1)//注意不能和前一个进行比较,因为前一个已经被赋值
poi[i].yy1 = m++;
else
poi[i].yy1 = m;
} sort(poi,poi+n,cmp1);
m=;
poi[n].xx1=Inf;
for(int i=; i<n; i++)
{
if(poi[i].xx1!=poi[i+].xx1)
poi[i].xx1 = m++;
else
poi[i].xx1 = m;
}
return ;
}
int tem[Max],minx[Max],pos[Max];
void Solve()
{
int sum;
memset(bit,,sizeof(bit));
for(int i=; i<n; i++) //边添加边查询
{
if(i!=&&poi[i].xx1==poi[i-].xx1)
sum++;
else
sum=;
poi[i].ldo=Sum(poi[i].yy1-)-sum;//减一,避免y轴相同的点被计算
poi[i].lup=Sum(n)-Sum(poi[i].yy1);
Add(poi[i].yy1);
} memset(bit,,sizeof(bit));
for(int i=n-; i>=; i--)
{
if(i!=n-&&poi[i].xx1==poi[i+].xx1)
sum++;
else
sum=;
poi[i].rdo=Sum(poi[i].yy1-);
poi[i].rup=Sum(n)-Sum(poi[i].yy1)-sum;
Add(poi[i].yy1);
} int manx=,mans;//统计
int coun=,cnt=;
minx[]=Inf;
for(int i=; i<n; i++)//计算最小值最大的是多少
{
if(!i||poi[i].xx1==poi[i-].xx1)
{
if(poi[i].rup+poi[i].ldo<minx[coun])
minx[coun]=poi[i].rup+poi[i].ldo;
}
else
{
manx=max(manx,minx[coun]);
pos[coun++]=i;//每条同x轴的最后一个的后一个下标
minx[coun]=Inf;
if(poi[i].rup+poi[i].ldo<minx[coun])
minx[coun]=poi[i].rup+poi[i].ldo;
}
}
pos[coun]=n;
manx=max(manx,minx[coun]); for(int i=;i<=coun;i++)
{
if(minx[i]==manx)//此x轴可用
{
mans=;
for(int j=i==?:pos[i-];j<pos[i];j++)
mans=max(mans,poi[j].lup+poi[j].rdo);
tem[cnt++]=mans;
}
} printf("Stan: %d; Ollie:",manx);
sort(tem,tem+cnt);
int cntt=;
for(int i=;i<cnt;i++)//去重
if(tem[i]!=tem[cntt])
tem[++cntt]=tem[i];
for(int i=; i<=cntt; i++)
printf(" %d",tem[i]);
printf(";\n");
return ;
}
int main()
{
while(~scanf("%d",&n)&&n)
{
for(int i=; i<n; i++)
scanf("%d %d",&poi[i].xx1,&poi[i].yy1);
Dtz();//离散化
Solve();
}
return ;
}

微信扫一扫

支付宝扫一扫

本文网址:https://www.zhankr.net/141496.html

相关推荐
python开发_常用的python模块及安装方法
adodb:我们领导推荐的数据库连接组件bsddb3:BerkeleyDB的连接组件Cheetah-1.0:我比较喜欢这个版本的cheeta…
日期:2022-11-24 点赞:875 阅读:5,067
Educational Codeforces Round 11 C. Hard Process 二分
C. Hard Process题目连接:http://www.codeforces.com/contest/660/problem/CDes…
日期:2022-11-24 点赞:806 阅读:3,504
下载Ubuntn 17.04 内核源代码
zengkefu@server1:/usr/src$ uname -aLinux server1 4.10.0-19-generic #21…
日期:2022-11-24 点赞:565 阅读:4,312
可用Active Desktop Calendar V7.86 注册码序列号
可用Active Desktop Calendar V7.86 注册码序列号Name: www.greendown.cn Code: &nb…
日期:2022-11-24 点赞:730 阅读:4,307
Android调用系统相机、自定义相机、处理大图片
Android调用系统相机和自定义相机实例本博文主要是介绍了android上使用相机进行拍照并显示的两种方式,并且由于涉及到要把拍到的照片显…
日期:2022-11-24 点赞:512 阅读:4,904
Struts的使用
一、Struts2的获取  Struts的官方网站为:http://struts.apache.org/  下载完Struts2的jar包,…
日期:2022-11-24 点赞:671 阅读:3,097
发表评论
暂无评论

还没有评论呢,快来抢沙发~

助力内容变现

将您的收入提升到一个新的水平

点击联系客服

在线时间:8:00-16:00

客服电话

400-888-8888

客服邮箱

ceotheme@ceo.com

扫描二维码

关注微信公众号

扫描二维码

手机访问本站