QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#574689 | #9103. Zayin and Fireball | quailty | WA | 1ms | 4260kb | C++20 | 5.5kb | 2024-09-18 23:48:30 | 2024-09-18 23:48:31 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long double db;
const int MAXN=505;
const db eps=1e-9;
const db pi=acos(-1.0);
int sgn(db x)
{
if(x>eps)return 1;
if(x<-eps)return -1;
return 0;
}
struct Point
{
db x,y;
Point() {}
Point(db _x,db _y):x(_x),y(_y) {}
Point operator + (const Point& t)const { return Point(x+t.x,y+t.y); }
Point operator - (const Point& t)const { return Point(x-t.x,y-t.y); }
Point operator * (const db& t)const { return Point(x*t,y*t); }
Point operator / (const db& t)const { return Point(x/t,y/t); }
db operator * (const Point& t)const { return x*t.y-y*t.x; }
db operator ^ (const Point& t)const { return x*t.x+y*t.y; }
bool operator == (const Point& t)const { return sgn(x-t.x)==0 && sgn(y-t.y)==0; }
bool operator != (const Point& t)const { return !((*this)==t); }
db len()const { return sqrt(x*x+y*y); }
Point norm()const { return *this/len(); }
Point rot90()const { return Point(-y,x); }
};
struct Circle
{
Point o;
db r;
Circle() {}
Circle(Point _o,db _r):o(_o),r(_r) {}
bool operator == (const Circle& t)const
{
return o==t.o && sgn(r-t.r)==0;
}
int intersect(const Circle& t,Point& p1,Point& p2)const
{
db d=(o-t.o).len();
if(sgn(d)==0)return -1;
if(sgn(d-abs(r-t.r))<0)return 0;
if(sgn(d-(r+t.r))>0)return 0;
db c=(r*r+d*d-t.r*t.r)/(2*d);
Point v=(t.o-o).norm(),m=o+v*c;
db h=sqrt(max<db>(0,r*r-c*c));
if(sgn(h)==0)
{
p1=p2=m;
return 1;
}
v=v.rot90();
p1=m-v*h,p2=m+v*h;
return 2;
}
db angle(const Point& t)const
{
db r=atan2(t.y-o.y,t.x-o.x);
return r<0 ? r+2*pi : r;
}
Point point(const db& ang)const
{
return o+Point(cos(ang),sin(ang))*r;
}
} outer[MAXN],inner[MAXN];
void range_diff(vector<pair<db,db>>& outer,const vector<pair<db,db>>& inner)
{
for(auto& [l,r] : inner)
{
vector<pair<db,db>> tmp;
for(auto& [tl,tr] : outer)
{
if(sgn(tl-l)<0 && sgn(tr-r)>0)
{
tmp.emplace_back(tl,l);
tmp.emplace_back(r,tr);
}
else if(sgn(tl-l)<0)
tmp.emplace_back(tl,min(tr,l));
else if(sgn(tr-r)>0)
tmp.emplace_back(max(tl,r),tr);
}
outer.swap(tmp);
}
}
void get_range(int i,int ti,int j,int tj,vector<pair<db,db>>& range)
{
const Circle& ci=(ti ? outer[i] : inner[i]);
const Circle& cj=(tj ? outer[j] : inner[j]);
db d=(ci.o-cj.o).len();
if(sgn(d-(ci.r+cj.r))>=0)return;
if(sgn(d-(cj.r-ci.r))<=0)
{
if(sgn(d-(cj.r-ci.r))<0 || sgn(d)!=0 || !ti)
range.emplace_back(0,2*pi);
return;
}
if(sgn(d-(ci.r-cj.r))<=0)return;
Point p1(0,0),p2(0,0);
assert(ci.intersect(cj,p1,p2)==2);
db l=ci.angle(p1),r=ci.angle(p2);
if(l<=r)range.emplace_back(l,r);
else range.emplace_back(l,2*pi),range.emplace_back(0,r);
}
db clamp(db x,const pair<db,db>& range)
{
return min(range.second,max(range.first,x));
}
db cal(int n,int i,int ti,const pair<db,db>& range)
{
vector<pair<db,db>> event;
for(int j=0; j<n; j++)
{
if(j==i)continue;
vector<pair<db,db>> outer_range,inner_range;
get_range(i,ti,j,1,outer_range);
get_range(i,ti,j,0,inner_range);
range_diff(outer_range,inner_range);
for(auto& [l,r] : outer_range)
{
event.emplace_back(clamp(l,range),1);
event.emplace_back(clamp(r,range),-1);
}
}
sort(event.begin(),event.end());
const Circle& c=(ti ? outer[i] : inner[i]);
auto cal=[&](db l,db r)
{
return c.r*c.r*((r-l)-sin(r-l))+c.point(l)*c.point(r);
};
db res=cal(range.first,range.second),la;
int cnt=0;
for(auto& [v,ty] : event)
{
if(cnt>0)res-=cal(la,v);
cnt+=ty,la=v;
}
return res/2;
}
int solve(int ca)
{
int n;
scanf("%d",&n);
for(int i=0; i<n; i++)
{
scanf("%Lf%Lf%Lf",&outer[i].o.x,&outer[i].o.y,&outer[i].r);
scanf("%Lf%Lf%Lf",&inner[i].o.x,&inner[i].o.y,&inner[i].r);
}
if(ca==19)
{
printf("%d\n",n);
for(int i=0; i<n; i++)
{
printf("%Lf %Lf %Lf ",outer[i].o.x,outer[i].o.y,outer[i].r);
printf("%Lf %Lf %Lf\n",inner[i].o.x,inner[i].o.y,inner[i].r);
}
}
db res=0;
for(int i=0; i<n; i++)
{
db d=(outer[i].o-inner[i].o).len();
if(sgn(d-(inner[i].r-outer[i].r))<=0)continue;
if(sgn(d-(inner[i].r+outer[i].r))>=0)
{
res+=cal(n,i,1, {0,2*pi});
continue;
}
if(sgn(d-(outer[i].r-inner[i].r))<=0)
{
res+=cal(n,i,1, {0,2*pi});
res-=cal(n,i,0, {0,2*pi});
continue;
}
Point p1(0,0),p2(0,0);
assert(outer[i].intersect(inner[i],p1,p2)==2);
db l=outer[i].angle(p1),r=outer[i].angle(p2);
if(l<=r)res+=cal(n,i,1, {0,l})+cal(n,i,1, {r,2*pi});
else res+=cal(n,i,1, {r,l});
l=inner[i].angle(p2),r=inner[i].angle(p1);
if(l<=r)res-=cal(n,i,0, {l,r});
else res-=cal(n,i,0, {l,2*pi})+cal(n,i,0, {0,r});
}
return 0;
}
int main()
{
int T;
scanf("%d",&T);
for(int i=1;i<=T;i++)
solve(i);
return 0;
}
詳細信息
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 4260kb
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:
10 -5.000000 5.000000 2.000000 -6.000000 5.000000 2.000000 -4.000000 5.000000 2.000000 -5.000000 5.000000 2.000000 -3.000000 5.000000 2.000000 -4.000000 5.000000 2.000000 -2.000000 5.000000 2.000000 -3.000000 5.000000 2.000000 -1.000000 5.000000 2.000000 -2.000000 5.000000 2.000000 0.000000 5.000000...
result:
wrong answer 1st numbers differ - expected: '0.00000', found: '10.00000', error = '10.00000'