【扫描线】Gym - 100781G - Goblin Garden Guards
2024-09-27 17:22:26
平面上有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;
}
最新文章
- JS--实现简单轮播(一)
- JS动态引入js,CSS——动态创建script/link/style标签
- Hasor-Core v0.0.4 &; Web v0.0.3 发布
- DataGridView 绑定List集合后实现自定义排序
- 【架构】RPC 使用 Haproxy、keepalive作为负载均衡
- I/O多路复用——epoll函数
- hadoop之JobTracker功能分析
- Android(java)学习笔记77:网络编程的概述
- HTML5 离线功能介绍
- nginx配置方法
- POJ 3280 Cheapest Palindrome (DP)
- 百度Web App在线生成平台Site App体验
- 获取当前用户的网络状态--iOS
- 任何一款IDE的设计思路
- 来杯咖啡看Pecan
- JavaScript正则表达式验证大全(收集)
- 用DDK开发的9054驱动 .
- maven的UnsupportedClassVersionError
- 【转】Android中保持Service的存活
- nvm的安装