平面上有100000个哥布林和20000个圆,问你不在圆内的哥布林有多少个。

将每个圆从左到右切2r+1次,形成(2r+1)*2个端点,将上端点记作入点,下端点记作出点,再将这些点和那些哥布林一起排序(x第一关键字,y第二关键字,类型(入 哥布林 出)第三关键字),扫一遍就好了。

#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const double EPS=0.00000001;
struct Point{
int x;
double y;
int type;
Point(const int &x,const double &y,const int &type){
this->x=x;
this->y=y;
this->type=type;
}
Point(){}
}p[405*20005+100005];
bool cmp(const Point &a,const Point &b){
return a.x!=b.x ? a.x<b.x : (fabs(a.y-b.y)>=EPS ? a.y>b.y : a.type<b.type);
}
double sqr(double x){
return x*x;
}
int n,m,e;
int main(){
scanf("%d",&n);
for(int i=1;i<=n;++i){
scanf("%d%lf",&p[i].x,&p[i].y);
p[i].type=1;
}
e=n;
int x;
double y,r;
scanf("%d",&m);
for(int i=1;i<=m;++i){
scanf("%d%lf%lf",&x,&y,&r);
for(int j=x-r;j<=x+r;++j){
double tmp=r*r-sqr(x-(double)j);
p[++e]=Point(j,sqrt(tmp)+y,0);
p[++e]=Point(j,-sqrt(tmp)+y,2);
}
}
sort(p+1,p+e+1,cmp);
int in=0,ans=0;
for(int i=1;i<=e;++i){
if(p[i].type==0){
++in;
}
else if(p[i].type==2){
--in;
}
else{
if(in==0){
++ans;
}
}
}
printf("%d\n",ans);
return 0;
}

最新文章

  1. JS--实现简单轮播(一)
  2. JS动态引入js,CSS——动态创建script/link/style标签
  3. Hasor-Core v0.0.4 &amp; Web v0.0.3 发布
  4. DataGridView 绑定List集合后实现自定义排序
  5. 【架构】RPC 使用 Haproxy、keepalive作为负载均衡
  6. I/O多路复用——epoll函数
  7. hadoop之JobTracker功能分析
  8. Android(java)学习笔记77:网络编程的概述
  9. HTML5 离线功能介绍
  10. nginx配置方法
  11. POJ 3280 Cheapest Palindrome (DP)
  12. 百度Web App在线生成平台Site App体验
  13. 获取当前用户的网络状态--iOS
  14. 任何一款IDE的设计思路
  15. 来杯咖啡看Pecan
  16. JavaScript正则表达式验证大全(收集)
  17. 用DDK开发的9054驱动 .
  18. maven的UnsupportedClassVersionError
  19. 【转】Android中保持Service的存活
  20. nvm的安装

热门文章

  1. mybatis 插入语句name no find
  2. G题 hdu 1466 计算直线的交点数
  3. 【Python学习】解决pandas中打印DataFrame行列显示不全的问题
  4. libsensor
  5. python之requests库使用问题汇总
  6. FISCO-BCOS平台共识
  7. 我的新博客地址http://xxxbw.github.io/
  8. 用指定jdk执行jar包
  9. Django视图之ORM数据库查询操作API
  10. WordPress 一键置顶文章(推荐用SM Sticky Clicky Star)