首页 > 其他分享 >圆的面积并(模板)

圆的面积并(模板)

时间:2022-11-05 20:01:03浏览次数:80  
标签:ch return int double 面积 st inline 模板

BZOJ

题意:给出\(n(n<=1000)\)个圆,每个圆给出圆心坐标\((x,y)\)和半径\(r\),求它们的面积并。

方法一:辛普森积分

本题用辛普森积分,精度eps开小会T一个点,开大会WA一个点;如果用上文中提到的自适应辛普森就会T很多点,因此这种方法时间复杂度不明确,取决于精度和数据强度。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline int read() {
	char ch = getchar(); int x = 0, f = 1;
	while (ch < '0' || ch>'9') { if (ch == '-') f = -1; ch = getchar(); }
	while ('0' <= ch && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
	return x * f;
}
const int N = 1e3 + 5;
const int M = 1e5 + 5;
const double eps=1e-8;
int n,bj[N];
struct Cir{int x,y,r;}p[N];
struct Line{double l,r;}S[N];
inline bool cmp_Cir(Cir a,Cir b){
	return a.r<b.r;
}
inline bool cmp_Line(Line a,Line b){
	return a.l<b.l;
}
inline int cmp(double x){
    if (x<=eps&&x>=-eps) return 0;
    return (x>0)?1:-1;
}
inline double Sqr(double x){return x*x;}
inline double f(double x){
	int top=0;
	for(int i=1;i<=n;++i)
		if(p[i].x-p[i].r<=x&&x<=p[i].x+p[i].r){
			double len=sqrt(Sqr(p[i].r)-Sqr(fabs(p[i].x-x)));
			S[++top]=(Line){p[i].y-len,p[i].y+len};
		}
	sort(S+1,S+top+1,cmp_Line);
	double ret=0,l=-1e9,r=-1e9;
	for(int i=1;i<=top;++i)
		if(S[i].l-r>eps)ret+=r-l,l=S[i].l,r=S[i].r;
		else if(S[i].r-r>eps)r=S[i].r;
	return ret+r-l;
}
inline double Simpson(double l,double r){return (r-l)*(f(l)+f(r)+4.0*f((l+r)/2.0))/6.0;}
inline double asr(double l,double r,double val){
	double mid=(l+r)/2.0;
	double lval=Simpson(l,mid),rval=Simpson(mid,r);
	if(cmp(lval+rval-val)==0){return val;}
	else return asr(l,mid,lval)+asr(mid,r,rval);
}
int main(){
	n=read();
	for(int i=1;i<=n;++i){
		p[i].x=read();
		p[i].y=read();
		p[i].r=read();
	}
	int l=1e9,r=-1e9;
	for(int i=1;i<=n;++i)l=min(l,p[i].x-p[i].r);
	for(int i=1;i<=n;++i)r=max(r,p[i].x+p[i].r);
	sort(p+1,p+n+1,cmp_Cir);
	for (int i=1;i<=n;++i)
        for (int j=i+1;j<=n;++j){
            if (cmp(sqrt(Sqr(p[i].x-p[j].x)+Sqr(p[i].y-p[j].y))+p[i].r-p[j].r)<=0){
                bj[i]=1;
                break;
            }
        }
    int m=0;
    for(int i=1;i<=n;++i)if(!bj[i])p[++m]=p[i];
    n=m;
	double ans=asr(l*1.0,r*1.0,Simpson(l,r));
	printf("%.3lf\n",ans);
	return 0;
}

方法二:格林公式

难得高数微积分知识还能派上用场,时间复杂度\(O(n^2logn)\)。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline int read() {
	char ch = getchar(); int x = 0, f = 1;
	while (ch < '0' || ch>'9') { if (ch == '-') f = -1; ch = getchar(); }
	while ('0' <= ch && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
	return x * f;
}
int n;
const int N=1005;
const double Pi=acos(-1.0);
struct Point{
    int x,y;
    inline Point(){}
    inline Point(int xx,int yy):x(xx),y(yy){}
    inline Point operator +(const Point &b)const{return Point(x+b.x,y+b.y);}
    inline Point operator -(const Point &b)const{return Point(x-b.x,y-b.y);}
    inline bool operator <(const Point &b)const{return x<b.x||(x==b.x&&y<b.y);}
    inline bool operator ==(const Point &b)const{return x==b.x&&y==b.y;}
};
struct Cir{
    Point p;int r;
    inline bool operator <(const Cir &b)const{return p<b.p||p==b.p&&r<b.r;}
    inline bool operator ==(const Cir &b)const{return p==b.p&&r==b.r;}
}c[N];
pair<double,int>st[N<<1];
inline double calc(double r,double x,double y,double t1,double t2){
	return r*(r*(t2-t1)+x*(sin(t2)-sin(t1))-y*(cos(t2)-cos(t1)));
}
double solve(int id){
    int top=0,cnt=0;
    for(int i=1;i<=n;++i){
    	if(i!=id){
	        double dis=sqrt((c[i].p.x-c[id].p.x)*(c[i].p.x-c[id].p.x)+(c[i].p.y-c[id].p.y)*(c[i].p.y-c[id].p.y));
	        if(c[id].r+dis<=c[i].r)return 0;
	        if(c[i].r+dis<=c[id].r||c[i].r+c[id].r<=dis)continue;
	        double del=acos((c[id].r*c[id].r+dis*dis-c[i].r*c[i].r)/(2*c[id].r*dis));
	        double ang=atan2(c[i].p.y-c[id].p.y,c[i].p.x-c[id].p.x);
	        double l=ang-del,r=ang+del;
	        if(l<-Pi)l+=2*Pi;if(r>=Pi)r-=2*Pi;
	        if(l>r)++cnt;
	        st[++top]=make_pair(l,1),st[++top]=make_pair(r,-1);
	    }
	}
    st[0]=make_pair(-Pi,0),st[++top]=make_pair(Pi,0);
    sort(st+1,st+1+top);
    double res=0;
    for(int i=1;i<=top;cnt+=st[i++].second)
        if(!cnt)res+=calc(c[id].r,c[id].p.x,c[id].p.y,st[i-1].first,st[i].first);
    return res;
}
int main(){
    n=read();
    for(int i=1;i<=n;++i){
    	c[i].p.x=read();
    	c[i].p.y=read();
    	c[i].r=read();
	}
    sort(c+1,c+1+n);
	n=unique(c+1,c+1+n)-c-1;
	double ans=0;
    for(int i=1;i<=n;++i)ans+=solve(i);
    printf("%.3lf\n",ans*0.5);
    return 0;
}

标签:ch,return,int,double,面积,st,inline,模板
From: https://www.cnblogs.com/PPXppx/p/16860951.html

相关文章

  • 【管理】日报,周报,会议记录模板
    目录​​日报怎么写​​​​会议记录模板​​日报怎么写重点:如果是同一个项目/问题,需要具有连贯性。(即解决了前面发现的哪些问题,或 问题、工程进度、百分比)记录过去发现和......
  • HTML期末作业——基于html实现娱乐音乐资讯发布平台HTML模板(22页面)
    ......
  • 模板匹配(createTrackbar函数这样用)
    一、模板匹配模板匹配(TemplateMatching)就是在一幅图像中寻找和模板图像(template)最相似的区域,该方法原理简单计算速度快,能够应用于目标识别,目标跟踪等多个领域。二、原理......
  • 模板层(5)
    模版语法传值{{}}:变量相关{%%}:逻辑相关defindex(request):#模版语法可以传递的后端python数据类型n=123f=11.11s='我也现'b=Tru......
  • P3376 【模板】网络最大流(EK)
    #include<iostream>#include<queue>#include<cstring>usingnamespacestd;constlonglongN=5e3+1;longlongh[N],to[N<<1],nt[N<<1],fro......
  • P3387 【模板】缩点
    #include<iostream>#include<queue>#include<vector>usingnamespacestd;constintN=1e4+1;intn,m;vector<int>to[N];intval[N];voidadd......
  • 解读Vue3模板编译优化
    今天的文章打算学习下Vue3下的模板编译与Vue2下的差异,以及VDOM下Diff算法的优化。编译入口了解过Vue3的同学肯定知道Vue3引入了新的组合Api,在组件mount阶......
  • python-求三角形的面积
    计算三角形的面积法一:#计算三角形的面积a=float(input('输入三角形第一边长:'))b=float(input('输入三角形第二边长:'))c=float(input('输入三角形第三边长:'))whilea......
  • P3865 【模板】ST表
    【模板】ST表题目背景这是一道ST表经典题——静态区间最大值请注意最大数据时限只有0.8s,数据强度不低,请务必保证你的每次查询复杂度为\(O(1)\)。若使用更高时间复......
  • 【单片机/嵌入式】【梁山派】学习日志02:工程模板创建
    工程模板创建一、新建工程目录1.1包含文件(1)Project:存放工程文件,编译文件等。(2)Firmware:存放ARM内核文件,标准外设库文件等。(3)Hardware:存放开发板的硬件驱动文件。(4)App......