QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#574689#9103. Zayin and FireballquailtyWA 1ms4260kbC++205.5kb2024-09-18 23:48:302024-09-18 23:48:31

Judging History

你现在查看的是测评时间为 2024-09-18 23:48:31 的历史记录

  • [2024-09-23 15:04:32]
  • 管理员手动重测本题所有提交记录
  • 测评结果:WA
  • 用时:1ms
  • 内存:4168kb
  • [2024-09-18 23:48:31]
  • 评测
  • 测评结果:0
  • 用时:1ms
  • 内存:4260kb
  • [2024-09-18 23:48:30]
  • 提交

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'