QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#465682#9103. Zayin and FireballQingyuWA 4316ms4264kbC++4.9kb2024-07-07 04:35:362024-07-07 04:35:38

Judging History

你现在查看的是测评时间为 2024-07-07 04:35:38 的历史记录

  • [2024-09-23 15:03:46]
  • 管理员手动重测本题所有提交记录
  • 测评结果:WA
  • 用时:1ms
  • 内存:4236kb
  • [2024-08-05 12:02:35]
  • 管理员手动重测该提交记录
  • 测评结果:100
  • 用时:4299ms
  • 内存:4284kb
  • [2024-07-07 04:35:38]
  • 评测
  • 测评结果:100
  • 用时:4316ms
  • 内存:4264kb
  • [2024-07-07 04:35:36]
  • 提交

answer

#include<stdio.h>
#include<cmath>
#include<vector>
#include<algorithm>
using namespace std;
#define pb(a) push_back(a)
#define fi first
#define se second
#define mp(a,b) make_pair(a,b)
typedef double type;
const type eps=1e-8,pi=acosl(-1);

inline type Sqrt(type x) {
	return x<0?0:sqrtl(x);
}

inline type pow(type x) {
	return x*x;
}

inline int dcmp(type x) {
	return (x>eps)-(x<-eps);
}

struct point {
	type x,y;
	point() {}
	point(type x,type y):x(x),y(y) {}
	friend bool operator == (const point &a,const point &b) {
		return dcmp(a.x-b.x)==0 && dcmp(a.y-b.y)==0;
	}
	friend bool operator < (const point &a,const point &b) {
		return a.x<b.x || a.x==b.x && a.y<b.y;
	}
	friend point operator + (const point &a,const point &b) {
		return point(a.x+b.x,a.y+b.y);
	}
	friend point operator - (const point &a,const point &b) {
		return point(a.x-b.x,a.y-b.y);
	}
	friend point operator *(const point &a,const type &b) {
		return point(a.x*b,a.y*b);
	}
	friend point operator / (const point &a,const type &b) {
		return point(a.x/b,a.y/b);
	}
};

inline type dis(const point &a,const point &b) {
	return Sqrt(pow(a.x-b.x)+pow(a.y-b.y));
}

inline point rotate(const point &p,type cost,type sint) {
	return point(p.x*cost-p.y*sint,p.x*sint+p.y*cost);
}

inline pair<point,point> crosspoint(point ap,type ar,point bp,type br) {
	type d=dis(ap,bp);
	type cost=(pow(ar)+pow(d)-pow(br))/(2*ar*d);
	type sint=Sqrt(1.-pow(cost));
	point v=(bp-ap)/d*ar;
	return make_pair(ap+rotate(v,cost,-sint),ap+rotate(v,cost,sint));
}

struct rd {
	point O,o;
	type D,d;
}R[505];

inline type atan2(const point &a) {
	return atan2l(a.y,a.x);
}

inline pair<point,point> cp(const point &o,type R,const point &O,type d) {
	pair<point,point> pr=crosspoint(o,R,O,d);
	point a=pr.first,b=pr.second;
	type ta=atan2(a-o),tb=atan2(b-o);
	if (tb<ta) tb+=2*pi;
	type mid=(ta+tb)/2;
	point mp=o+point(R*cosl(mid),R*sinl(mid));
	if (dis(mp,O)-eps>d) {
		swap(a,b);
		swap(ta,tb);
	}
	return make_pair(a,b);
}

vector<pair<type,int> > tmp,tmpinte;

inline void push(type l,type r,vector<pair<type,int> > &tmp,int del=1) {
	if (l<r+eps) {
		tmp.push_back(make_pair(l,del));
		tmp.push_back(make_pair(r,-del));
	}
	else {
		tmp.push_back(make_pair(l,del));
		tmp.push_back(make_pair(pi,-del));
		tmp.push_back(make_pair(-pi,del));
		tmp.push_back(make_pair(r,-del));
	}
}

inline void cal(const point &o,type R,const rd &A) {
	bool outer,inner;
	type D=dis(o,A.O),d=dis(o,A.o);
	outer=(fabsl(D-A.D)<R-eps && R+eps<D+A.D);
	inner=(fabsl(d-A.d)<R-eps && R+eps<d+A.d);
	if (!inner && !outer) {
		if ((d+A.d<R+eps || R+A.d<d+eps) && R+D<A.D+eps) push(-pi,pi,tmpinte);
	}
	if (inner && !outer) if (R+D<A.D+eps) {
		pair<point,point> p=cp(o,R,A.o,A.d);
		point a=p.first,b=p.second;
		type ta=atan2(a-o),tb=atan2(b-o);
		push(tb,ta,tmpinte);
	}
	if (!inner && outer) if (A.d+eps<R+d) {
		pair<point,point> p=cp(o,R,A.O,A.D);
		point a=p.first,b=p.second;
		type ta=atan2(a-o),tb=atan2(b-o);
		push(ta,tb,tmpinte);
	}
	if (inner && outer) {
		tmp.clear();
		pair<point,point> p1=cp(o,R,A.o,A.d);
		point a1=p1.first,b1=p1.second;
		type ta1=atan2(a1-o),tb1=atan2(b1-o);
		push(ta1,tb1,tmp,-1);
		pair<point,point> p2=cp(o,R,A.O,A.D);
		point a2=p2.first,b2=p2.second;
		type ta2=atan2(a2-o),tb2=atan2(b2-o);
		push(ta2,tb2,tmp);
		sort(tmp.begin(),tmp.end());
		tmp.push_back(make_pair(pi,0));
		type lst=-pi;
		int now=0;
		for (auto v:tmp) {
			if (now>0 && lst+eps<v.first) push(lst,v.first,tmpinte);
			lst=v.first;
			now+=v.second;
		}
	}
}

inline type inte(int i,int op,int n) {
	tmpinte.clear();
	point o=R[i].o,O=R[i].O;
	type d=R[i].d,D=R[i].D;
	if (op==0) {
		for (int j=1;j<=n;j++) if (i!=j) cal(O,D,R[j]);
		type Dis=dis(o,O);
		if (fabsl(Dis-D)+eps<d && d+eps<Dis+D){
			pair<point,point> p=cp(O,D,o,d);
			point a=p.first,b=p.second;
			type ta=atan2(a-O),tb=atan2(b-O);
			push(ta,tb,tmpinte);
		}
		if (Dis+D<d+eps) push(-pi,pi,tmpinte);
	}
	else {
		for (int j=1;j<=n;j++) if (i!=j) cal(o,d,R[j]);
		type Dis=dis(o,O);
		if (fabsl(Dis-D)+eps<d && d+eps<Dis+D){
			pair<point,point> p=cp(o,d,O,D);
			point a=p.first,b=p.second;
			type ta=atan2(a-o),tb=atan2(b-o);
			push(tb,ta,tmpinte);
		}
		if (Dis+D<d+eps || D+d<Dis+eps) push(-pi,pi,tmpinte);
	}
	sort(tmpinte.begin(),tmpinte.end());
	tmpinte.push_back(make_pair(pi,0));
	type lst=-pi,rt=0;
	int now=0;
	for (auto v:tmpinte) {
		if (!now) rt+=(op==0)?O.y*D*(cosl(v.first)-cosl(lst))-pow(D)/2*(v.first-lst)+pow(D)/4*(sinl(2*v.first)-sinl(2*lst))
				             :o.y*d*(cosl(v.first)-cosl(lst))-pow(d)/2*(v.first-lst)+pow(d)/4*(sinl(2*v.first)-sinl(2*lst));
		lst=v.first;
		now+=v.second;
	}
	return rt;
}

inline void solve() {
	int n;
	scanf("%d",&n);
	for (int i=1;i<=n;i++) {
		double x,y,X,Y,D,d;
		scanf("%lf%lf%lf%lf%lf%lf",&X,&Y,&D,&x,&y,&d);
		R[i]=(rd){point(X,Y),point(x,y),D,d};
	}
	type ans=0;
	for (int i=1;i<=n;i++) ans-=inte(i,0,n);
	for (int i=1;i<=n;i++) ans+=inte(i,1,n);
	printf("%.6lf\n",double(ans));
}

int main() {
	int T;
	scanf("%d",&T);
	for (int t=1;t<=T;t++) solve();
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 4264kb

input:

22
1
0 0 1 0 0 1
1
0 0 2 0 0 1
1
0 0 2 1 0 1
1
0 0 2 2 0 1
1
0 0 2 1 0 2
2
0 0 1 0 0 0
0 0 3 0 0 2
2
0 0 1 0 0 0
0 0 3 0 0 1
2
-233 0 3 -234 0 1
233 0 2 231 0 1
2
0 0 1 0 0 0
1 0 3 0 0 1
2
0 0 1 0 0 0
0 2 3 0 0 1
2
2 4 2 2 4 1
3 3 3 3 3 1
4
0 1 1 0 2 2
3 3 3 3 4 2
250 2 4 0 0 100
255 7 12 254 10 4
3...

output:

0.000000
9.424778
9.424778
11.163304
3.957934
18.849556
28.274334
36.296045
28.274334
28.274334
28.157137
417.831823
38.218848
125660.564551
125660.564551
125660.564789
125660.564789
31412.784943
78.317303
301.267454
18751.965611
70.914255

result:

ok 22 numbers

Test #2:

score: 0
Accepted
time: 4316ms
memory: 4244kb

input:

30
500
129 442 8 147 446 7
131 405 28 110 416 4
164 446 3 146 456 0
166 453 20 152 423 24
100 417 25 164 439 5
119 425 7 115 420 19
127 408 5 107 423 18
157 449 18 148 444 16
178 392 10 134 456 27
162 419 25 124 456 15
133 425 6 119 444 16
132 412 5 127 464 28
139 373 19 148 414 9
114 425 2 117 431 ...

output:

16325.897819
3633664.465841
213359.268322
222590.371031
215595.956055
233363.113815
3014984.870782
16169.051248
3524934.377027
226126.671103
219815.065403
215704.473090
241176.720628
2912302.913357
16386.416990
3396240.037947
231041.717371
209140.296477
203275.021880
217322.235500
3172667.464499
161...

result:

ok 30 numbers