QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#465682 | #9103. Zayin and Fireball | Qingyu | WA | 4299ms | 4284kb | C++ | 4.9kb | 2024-07-07 04:35:36 | 2024-08-05 12:02:35 |
Judging History
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: 4299ms
memory: 4284kb
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