首页 > 代码库 > 【扫描线】Gym - 100781G - Goblin Garden Guards
【扫描线】Gym - 100781G - Goblin Garden Guards
平面上有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; }
【扫描线】Gym - 100781G - Goblin Garden Guards
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。