首页 技术 正文
技术 2022年11月23日
0 收藏 968 点赞 3,742 浏览 2155 个字

扫描线的应用。

扫描线就是用数据结构维护一个相对的顺序不变,带修改的东西。

通常只用于一次询问的情况。

抽象的看做一条垂直于x轴直线从左向右扫过去。

这道题目要求求出所有圆的异或并。

所以我们可以求出每一个圆的系数,然后乘上他们的面积。

由于不会出现相交的情况,所以圆弧的相对顺序是不变的。

所以我们用扫描线加入的时候,讨论一下上面的圆弧分别是上下半圆的情况。

然后比较容易的得出结论。

如果是上半圆,这个圆就属于它。

如果是下半弧,那么和它的包含性相同。

接下来找到它的父亲就可以了。

然后用set来维护这条扫描线,比较函数是计算交点的。

然后需要注意一下精度的处理,以及排序的时候第一关键字和第二关键字。

最后计算答案即可。

#include <set>
#include <map>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define F(i,j,k) for (int i=j;i<=k;++i)
#define D(i,j,k) for (int i=j;i>=k;--i)
#define ll long long
#define maxn 200005ll n,top=0,cal[maxn],T;struct Circle{
ll x,y,r;
Circle (){}
Circle (ll _x,ll _y,ll _r) {x=_x;y=_y;r=_r;}
void read(){scanf("%lld%lld%lld",&x,&y,&r);}
}a[maxn];struct Events{
ll id,d;
Events(){}
Events(ll _id,ll _d){id=_id;d=_d;}
void print()
{
printf("By Circle %lld Do %lld\n",id,d);
}
}b[maxn<<1];#define eps 1e-8int fcmp(double a)
{
return a<-eps?-1:a>eps;
}struct Node{
ll x,y,r,tag,id;
Node () {}
Node (ll _x,ll _y,ll _r,ll _tag,ll _id) {x=_x;y=_y;r=_r;tag=_tag;id=_id;}
void print()
{
printf("At ( %lld, %lld, %lld) Tag %lld\n",x,y,r,tag);
}
bool operator < (const Node & b) const{
double ya,yb;
ya=1.0*r*r-1.0*(T-x)*(T-x);
ya=1.0*y+1.0*tag*sqrt(ya);
yb=1.0*b.r*b.r-1.0*(T-b.x)*(T-b.x);
yb=1.0*b.y+1.0*b.tag*sqrt(yb);
return fcmp(ya-yb)==0?tag<b.tag:fcmp(ya-yb)<0;
}
};set <Node> s;bool cmpb(Events first,Events second)
{
ll lf=a[first.id].x-a[first.id].r*first.d,ls=a[second.id].x-a[second.id].r*second.d;
return lf==ls?first.d==second.d?a[first.id].y<a[second.id].y:first.d<second.d:lf<ls;
}void Add(int id,int d)
{
Node P;
if (d==1)
{
P=Node(a[id].x,a[id].y,a[id].r,1,id); s.insert(P);
P=Node(a[id].x,a[id].y,a[id].r,-1,id);s.insert(P);
}
else
{
P=Node(a[id].x,a[id].y,a[id].r,1,id); s.erase(P);
P=Node(a[id].x,a[id].y,a[id].r,-1,id);s.erase(P);
}
}ll query(ll x,ll y)
{
T=x;
Node now=Node(x,y,0,1,1);
Node pre=(*(s.upper_bound(now)));
if (pre.tag==1)
return -cal[pre.id];
else
return cal[pre.id];
}int main()
{
scanf("%lld",&n);
F(i,1,n) a[i].read(); a[++n]=Circle(0,0,3e8);
F(i,1,n) b[++top]=Events(i,1),b[++top]=Events(i,-1);
sort(b+1,b+top+1,cmpb);
cal[n]=-1;Add(n,1);
F(i,2,top-1)
{
if (b[i].d==1) cal[b[i].id]=query(a[b[i].id].x-a[b[i].id].r,a[b[i].id].y);
Add(b[i].id,b[i].d);
}
Add(n,-1);
ll ans=0;
F(i,1,n-1) ans+=cal[i]*a[i].r*a[i].r;
printf("%lld\n",ans);
}

微信扫一扫

支付宝扫一扫

本文网址:https://www.zhankr.net/140968.html

相关推荐
python开发_常用的python模块及安装方法
adodb:我们领导推荐的数据库连接组件bsddb3:BerkeleyDB的连接组件Cheetah-1.0:我比较喜欢这个版本的cheeta…
日期:2022-11-24 点赞:878 阅读:7,142
Educational Codeforces Round 11 C. Hard Process 二分
C. Hard Process题目连接:http://www.codeforces.com/contest/660/problem/CDes…
日期:2022-11-24 点赞:807 阅读:4,476
下载Ubuntn 17.04 内核源代码
zengkefu@server1:/usr/src$ uname -aLinux server1 4.10.0-19-generic #21…
日期:2022-11-24 点赞:567 阅读:5,291
可用Active Desktop Calendar V7.86 注册码序列号
可用Active Desktop Calendar V7.86 注册码序列号Name: www.greendown.cn Code: &nb…
日期:2022-11-24 点赞:733 阅读:5,163
Android调用系统相机、自定义相机、处理大图片
Android调用系统相机和自定义相机实例本博文主要是介绍了android上使用相机进行拍照并显示的两种方式,并且由于涉及到要把拍到的照片显…
日期:2022-11-24 点赞:512 阅读:6,335
Struts的使用
一、Struts2的获取  Struts的官方网站为:http://struts.apache.org/  下载完Struts2的jar包,…
日期:2022-11-24 点赞:671 阅读:3,875