题意:二维平面上有两个框,问平面被分成了几个部分

x,y<=1e9

思路:分类讨论可以

但数据范围实在太小了,离散化以后随便dfs一下

 #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<ll,ll> Pll;
typedef vector<int> VI;
typedef vector<PII> VII;
#define N 110000
#define M 4100000
#define fi first
#define se second
#define MP make_pair
#define pi acos(-1)
#define mem(a,b) memset(a,b,sizeof(a))
#define rep(i,a,b) for(int i=(int)a;i<=(int)b;i++)
#define per(i,a,b) for(int i=(int)a;i>=(int)b;i--)
#define lowbit(x) x&(-x)
#define Rand (rand()*(1<<16)+rand())
#define id(x) ((x)<=B?(x):m-n/(x)+1)
#define ls p<<1
#define rs p<<1|1 const ll MOD=1e9+,inv2=(MOD+)/;
double eps=1e-;
int INF=1e9;
int dx[]={-,,,};
int dy[]={,,-,}; int read()
{
int v=,f=;
char c=getchar();
while(c<||<c) {if(c=='-') f=-; c=getchar();}
while(<=c&&c<=) v=(v<<)+v+v+c-,c=getchar();
return v*f;
} struct arr
{
int x,id;
}x[],y[];
int b[][],c[],d[]; bool cmp(arr a,arr b)
{
return a.x<b.x;
} void dfs(int x,int y)
{
//printf("x=%d y=%d\n",x,y);
b[x][y]=;
rep(i,,)
{
int ux=x+dx[i],uy=y+dy[i];
if(ux>&&ux<&&uy>&&uy<&&b[ux][uy]==) dfs(ux,uy);
}
} int main()
{
//freopen("1.in","r",stdin);
int cas;
scanf("%d",&cas);
while(cas--)
{
x[].x=read(),y[].x=read(),x[].x=read(),y[].x=read();
x[].x=read(),y[].x=read(),x[].x=read(),y[].x=read();
rep(i,,)
{
x[i].id=y[i].id=i;
}
sort(x+,x++,cmp);
sort(y+,y++,cmp);
int m1=,m2=;
c[x[].id]=;
d[y[].id]=;
rep(i,,)
{
if(x[i].x==x[i-].x) c[x[i].id]=m1;
else
{
m1+=;
c[x[i].id]=++m1;
}
if(y[i].x==y[i-].x) d[y[i].id]=m2;
else
{
m2+=;
d[y[i].id]=++m2;
}
}
rep(i,,)
rep(j,,) b[i][j]=;
rep(i,d[],d[]) b[c[]][i]=b[c[]][i]=;
rep(i,d[],d[]) b[c[]][i]=b[c[]][i]=;
rep(i,c[],c[]) b[i][d[]]=b[i][d[]]=;
rep(i,c[],c[]) b[i][d[]]=b[i][d[]]=;
int ans=;
rep(i,,)
rep(j,,)
if(b[i][j]==)
{
ans++;
dfs(i,j);
} printf("%d\n",ans); } return ;
}

最新文章

  1. android include进来的组件 调用其子元素
  2. 清北学堂模拟赛day7 数字碰撞
  3. C++ STL之vector用法总结
  4. 无法进入adb shell,提示unknown host service的解决办法
  5. linux永久更改eth0的ip地址后仍然ping不通过
  6. BZOJ2961: 共点圆
  7. 转】启动tomcat时 错误: 代理抛出异常 : java.rmi.server.ExportException: Port already in use: 1099的解决办法
  8. 关于Android WebView内容不同屏幕兼容处理
  9. ios8 swift开发:显示变量的类名称
  10. Flex4 Alert PopupManager 演示样本
  11. 谈谈语音通信中的各种tone
  12. Java多线程与并发面试题
  13. C#3.0智能的编译器
  14. 002dayPython学习编码
  15. php-fpm重启
  16. 转Centos7.0进入单用户模式修改root密码
  17. Spring Cloud Alibaba Sentinel 整合 Feign 的设计实现
  18. less点滴
  19. cdnbest区域自定义配置里添加防xss攻击配置
  20. Intel处理器缺货将会持续到2019年第二季度!

热门文章

  1. 阶段1 语言基础+高级_1-3-Java语言高级_1-常用API_1_第6节 static静态_11_静态static关键字概述
  2. dcef3 为按钮添加单击事件
  3. Java ——修饰符 包 Bean
  4. 【ABAP系列】SAP ABAP 生成随机数的函数
  5. c#工厂模式
  6. web 前端1 拾遗
  7. PyTorch笔记之 scatter() 函数
  8. npm基本介绍及使用
  9. 使用IntelliJ IDEA配置Tomcat(详细操作)
  10. [CQOI2009]dance跳舞(最大流+二分)