题意:给你一个n*m的的矩形框 现在又k条射线 问这个矩形框会被分为多少个区域

思路:之前的想法是枚举边界然后线段树扫一遍计算一下矩形个数 复杂度果断不行 后面发现其实答案就是交点数+1 然后就用线段树上下扫两边

#include <bits/stdc++.h>
using namespace std;
const double pi = acos(-1.0);
const int N = 1e5+7;
const int inf = 0x3f3f3f3f;
typedef long long ll;
const ll mod = 1e7+9;
struct tree{
int l,r,v;
};
tree t[N<<2];
struct node{
int x,y,z;
}up[N],down[N];
int xx[N];
bool cmp1(node a,node b){
return a.y<b.y; //升
}
bool cmp2(node a,node b){
return a.y>b.y; //降
}
void build(int p,int l,int r){
t[p].l=l; t[p].r=r; t[p].v=0;
if(l==r){
return ;
}
int mid=(l+r)>>1;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
t[p].v=t[p<<1].v+t[p<<1|1].v; }
void update(int p,int x,int v){
if(t[p].l==t[p].r&&t[p].l==x){
t[p].v+=v;
return ;
}
int mid=(t[p].l+t[p].r)>>1;
if(x<=mid) update(p<<1,x,v);
else update(p<<1|1,x,v);
t[p].v=t[p<<1].v+t[p<<1|1].v;
}
ll query(int p,int l,int r){
if(l<=t[p].l&&t[p].r<=r){
return t[p].v;
}
int mid=(t[p].l+t[p].r)>>1;
ll res=0;
if(l<=mid) res+=query(p<<1,l,r);
if(r>mid) res+=query(p<<1|1,l,r);
return res;
}
int getpo(int x,int n){
int po=lower_bound(xx,xx+n,x)-xx+1;
return po;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int t; cin>>t;
while(t--){
int n,m,k; cin>>n>>m>>k;
int cnt=0; int cntup=0; int cntdown=0;
xx[cnt++]=1; xx[cnt++]=n-1;
for(int i=1;i<=k;i++){
int x,y; char ty;
cin>>x>>y>>ty;
xx[cnt++]=x;
if(ty=='U'){
up[cntup++]=node{x,y,1};
}else if(ty=='D'){
down[cntdown++]=node{x,y,1};
}else if(ty=='L'){
up[cntup++]=node{x,y,0};
down[cntdown++]=node{x,y,0};
}else{
up[cntup++]=node{x,y,3};
down[cntdown++]=node{x,y,3};
}
}
sort(xx,xx+cnt);
cnt=unique(xx,xx+cnt)-xx;
sort(up,up+cntup,cmp1);
sort(down,down+cntdown,cmp2);
build(1,1,cnt);
ll ans=1;
for(int i=0;i<cntup;i++){
if(up[i].z==1){
int po=getpo(up[i].x,cnt);
update(1,po,1);
}else if(up[i].z==0){
int l=getpo(1,cnt); int r=getpo(up[i].x,cnt);
ans+=query(1,l,r);
}else{
int l=getpo(up[i].x,cnt); int r=getpo(n-1,cnt);
ans+=query(1,l,r);
}
}
build(1,1,cnt);
for(int i=0;i<cntdown;i++){
if(down[i].z==1){
int po=getpo(down[i].x,cnt);
update(1,po,1);
}else if(down[i].z==0){
int l=getpo(1,cnt); int r=getpo(down[i].x,cnt);
ans+=query(1,l,r);
}else{
int l=getpo(down[i].x,cnt); int r=getpo(n-1,cnt);
ans+=query(1,l,r);
}
}
cout<<ans<<endl;
}
}

最新文章

  1. download github files
  2. Vue2.0 + Element-UI + WebAPI实践:简易个人记账系统
  3. Android 5.x特性概览四
  4. mysql线上一些隐患查询sql
  5. php对象引用和析构函数的关系
  6. Java基础之读文件——使用缓冲读取器读取文件(ReaderInputFromFile)
  7. CSS学习进度备忘
  8. NFS参数配置详细说明
  9. spring+ibatis环境搭建
  10. SQL Server 中各个系统表的作用
  11. 【protobuf进阶】通过.proto文件导出C#支持的.cs类文件
  12. 《Unity3D-播放被打中的时候粒子的特效的代码》
  13. HDU5410--01背包+完全背包
  14. AL32UTF8 and UTF8 and ZHS16GBK
  15. 深入分析Java I/O的工作机制 (一)
  16. FastDFS整合nginx后,nginx一直报错
  17. libmongoc关于\$pullAll和\$addToSet的一个使用问题记录
  18. Arcengine 在SDE创建数据集提示应用程序未获得创建或修改此类型数据的方案的许可
  19. OneZero第三周第四次站立会议(2016.4.7)
  20. cnn的说明

热门文章

  1. #1使用html+css+js制作网站教程 准备
  2. 【SpringBoot1.x】SpringBoot1.x 开发热部署和监控管理
  3. MySQL select 子查询的使用
  4. 通过show status 命令了解各种sql的执行频率
  5. zabbix的汉化
  6. 如果数据库上的row格式是mixed或者mixed的格式,如何对比两台数据库服务器上的数据是否一致呢
  7. js reduce数组转对象
  8. Doris
  9. Spring Bean详解
  10. ././include/linux/kconfig.h:4:32: fatal error: generated/autoconf.h: No such file or directory 解决办法