QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#856174#9728. Catch the StaryylxWA 37ms3968kbC++175.6kb2025-01-13 17:38:002025-01-13 17:38:01

Judging History

This is the latest submission verdict.

  • [2025-01-13 17:38:01]
  • Judged
  • Verdict: WA
  • Time: 37ms
  • Memory: 3968kb
  • [2025-01-13 17:38:00]
  • Submitted

answer

#include <bits/stdc++.h>
#define M_PI 3.14159265358979323846

using namespace std;

struct point {double x,y;};
struct line {point h,t;}; const line x_axis={{0,0},{1,0}};
struct circle{point o;double r;};
const double eps=1e-15;

int t,n,l,r,s,cnt,f,F;
double x,y,op;
vector<point> st,ms;
vector<pair<double,int> > p;

point operator+(point a,point b) {return (point){a.x+b.x,a.y+b.y};}
point operator-(point a,point b) {return (point){a.x-b.x,a.y-b.y};}
point operator*(double b,point a) {return (point){a.x*b,a.y*b};}
point operator/(point a,double b) {return (point){a.x/b,a.y/b};}

double dot(point a,point b) {return a.x*b.x+a.y*b.y;}    
double cx(point a,point b) {return a.x*b.y-a.y*b.x;}      
double len(point a) {return sqrt(a.x*a.x+a.y*a.y);}     
bool is_left(point a,point b) {return cx(a,b)<0;}        
bool is_right(point a,point b) {return cx(a,b)>0;}       
bool is_para(point a,point b) {return fabs(cx(a,b))<eps && dot(a,b)>=0;}   
bool is_verti(point a,point b) {return fabs(dot(a,b))<eps;}   
double angle(point a,point b) {return acos(dot(a,b)/len(a)/len(b));}             
double angle(point a) {return a.y>=0 ? angle(a,{1,0}) : M_PI*2-angle(a,{1,0});}    
double left_angle(point a,point b) {return is_right(a,b) ? 2*M_PI-angle(a,b) : angle(a,b);}

bool is_left(point b, line a) {return is_left(b-a.h,a.t-a.h);} 
bool is_right(point b, line a) {return is_right(b-a.h,a.t-a.h);} 

point inter(point a,point b,point c,point d) {return a+(cx(a-c,d-c)/cx(d-c,b-a))*(b-a);} 
point inter(line a,point b,point c) {return inter(a.h,a.t,b,c);}
point inter(line a,line b) {return inter(a.h,a.t,b.h,b.t);}

void tangent(vector<point> &ps1,vector<point> &ps2)
{
    int n1=ps1.size(),n2=ps2.size(),l,r1,r2,r,nxt,f1=0,f2=0;
    line l1,l2;
    l=r=0;
    while(is_left(ps1[(l+n1-1)%n1],{ps1[l],ps2[r]}) || is_left(ps1[(l+1)%n1],{ps1[l],ps2[r]}) || is_right(ps2[(r+n2-1)%n2],{ps1[l],ps2[r]}) || is_right(ps2[(r+1)%n2],{ps1[l],ps2[r]}))
    {
        while(is_left(ps1[(l+n1-1)%n1],{ps1[l],ps2[r]}) || is_left(ps1[(l+1)%n1],{ps1[l],ps2[r]}))
        {
            if(is_left(ps1[(l+1)%n1],{ps1[l],ps2[r]})) l=(l+1)%n1;
            else l=(l+n1-1)%n1;
        }
        while(is_right(ps2[(r+n2-1)%n2],{ps1[l],ps2[r]}) || is_right(ps2[(r+1)%n2],{ps1[l],ps2[r]}))
        {
            if(is_right(ps2[(r+1)%n2],{ps1[l],ps2[r]})) r=(r+1)%n2;
            else r=(r+n2-1)%n2;
        }
    }
    r2=r;
    l2={ps1[l],ps2[r]};
    l=r=0;
    while(is_right(ps1[(l+n1-1)%n1],{ps1[l],ps2[r]}) || is_right(ps1[(l+1)%n1],{ps1[l],ps2[r]}) || is_left(ps2[(r+n2-1)%n2],{ps1[l],ps2[r]}) || is_left(ps2[(r+1)%n2],{ps1[l],ps2[r]}))
    {
        while(is_right(ps1[(l+n1-1)%n1],{ps1[l],ps2[r]}) || is_right(ps1[(l+1)%n1],{ps1[l],ps2[r]}))
        {
            if(is_right(ps1[(l+1)%n1],{ps1[l],ps2[r]})) l=(l+1)%n1;
            else l=(l+n1-1)%n1;
        }
        while(is_left(ps2[(r+n2-1)%n2],{ps1[l],ps2[r]}) || is_left(ps2[(r+1)%n2],{ps1[l],ps2[r]}))
        {
            if(is_left(ps2[(r+1)%n2],{ps1[l],ps2[r]})) r=(r+1)%n2;
            else r=(r+n2-1)%n2;
        }
    }
    r1=r;
    l1={ps2[r],ps1[l]};
    if(l1.h.y>l1.t.y)
    {
        if(l1.h.y<0) {p.push_back(make_pair(inter(l1,x_axis).x,1));f1=1;}
        else if(l1.h.y==0 && ps2[(r1+1)%n2].y<0) {f1=1,p.push_back(make_pair(inter(l1,x_axis).x,1));}
    }
    else if(l1.h.y<l1.t.y)
    {
        if(l1.h.y>0) {f2=1;p.push_back(make_pair(inter(l1,x_axis).x,-1));}
        else if(l1.h.y==0 && ps2[(r1+1)%n2].y>0) {p.push_back(make_pair(inter(l1,x_axis).x,-1));f2=1;}
    }
    if(l2.h.y>l2.t.y && l2.t.y>0) {f1=1;p.push_back(make_pair(inter(l2,x_axis).x,1));}
    else if(l2.h.y<l2.t.y && l2.t.y<0) {f2=1,p.push_back(make_pair(inter(l2,x_axis).x,-1));}
    for(int i=r1;i!=r2;i=nxt)
    {
        nxt=(i+1)%n2;
        if(ps2[i].y>ps2[nxt].y && ps2[i].y>0) 
        {
            if(ps2[nxt].y<0) {f1=1,p.push_back(make_pair(inter(x_axis,ps2[i],ps2[nxt]).x,1));}
            else if(ps2[nxt].y==0 && ps2[(nxt+1)%n2].y<0) {f1=1,p.push_back(make_pair(inter(x_axis,ps2[i],ps2[nxt]).x,1));}
        }
        else if(ps2[i].y<ps2[nxt].y && ps2[i].y<0)
        {
            if(ps2[nxt].y>0) {f2=1,p.push_back(make_pair(inter(x_axis,ps2[i],ps2[nxt]).x,-1));}
            else if(ps2[nxt].y==0 && ps2[(nxt+1)%n2].y>0) {f2=1,p.push_back(make_pair(inter(x_axis,ps2[i],ps2[nxt]).x,-1));}
        }
    }
    if(f1!=f2)
    {
        if(f1==0) p.push_back(make_pair(-1e9-1,1));
        else p.push_back(make_pair(1e9+1,-1));
    }
}

bool cmp(pair<double,int> a,pair<double,int> b)
{
    return fabs(a.first-b.first)>eps ? a.first<b.first : a.second<b.second;
}

void solve()
{
    scanf("%d%d%d",&n,&l,&r);
    st.clear();
    op=0;
    cnt=0;
    f=0;
    F=0;
    p.clear();
    scanf("%d",&s);
    for(int i=0;i<s;i+=1)
    {
        scanf("%lf%lf",&x,&y);
        st.push_back({x,y});
    }
    for(int j=0;j<n;j+=1)
    {
        ms.clear();
        scanf("%d",&s);
        for(int i=0;i<s;i+=1)
        {
            scanf("%lf%lf",&x,&y);
            ms.push_back({x,y});
        }
        tangent(st,ms);
    }
    p.push_back(make_pair(l,2));
    p.push_back(make_pair(r,-2));
    sort(p.begin(),p.end(),cmp);
    for(int i=0;i<p.size()-1;i+=1)
    {
        if(p[i].second==1 || p[i].second==-1) cnt+=p[i].second;
        else if(p[i].second==2) f=1;
        else f=0;
        if(f==1 && cnt==0)
        {
            F=1;
            op+=p[i+1].first-p[i].first;
        }
    }
    if(F==1) printf("%.11lf\n",op);
    else printf("%d\n",-1);
}

int main()
{
    scanf("%d",&t);
    while(t--) solve();
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3968kb

input:

2
4 -8 8
3 -7 7 -6 8 -7 8
3 -9 -2 -7 3 -9 -1
3 -2 3 0 2 -4 5
3 5 1 5 3 4 2
3 1 -1 2 -2 3 -1
5 -8 8
5 -14 -3 -10 -2 -9 2 -10 4 -12 5
3 -16 0 -15 0 -15 1
3 -15 6 -9 5 -15 7
3 -10 5 -9 5 -10 6
3 -7 3 -3 2 -8 4
3 -6 -1 -6 -2 -5 -1

output:

9.40476190476
6.00000000000

result:

ok 2 numbers

Test #2:

score: 0
Accepted
time: 0ms
memory: 3968kb

input:

3
1 -4 4
3 -2 6 0 5 2 6
3 -3 1 3 1 0 4
3 -2 2
3 -2 4 2 4 0 6
3 -2 2 -1 2 -2 3
3 1 2 2 2 2 3
3 -2 -1 0 -3 2 -1
1 1 2
3 -8 0 -7 0 -8 1
3 -5 0 -4 -1 -4 0

output:

-1
0.00000000000
1.00000000000

result:

ok 3 numbers

Test #3:

score: 0
Accepted
time: 0ms
memory: 3840kb

input:

1
1 -744567334 955216804
5 -781518205 -852078097 -781516900 -852078384 -781516392 -852076569 -781518329 -852076047 -781519925 -852077600
5 -393011614 -131855702 -393010699 -131856607 -393008846 -131856475 -393009388 -131854587 -393010201 -131854694

output:

1699779738.69197916985

result:

ok found '1699779738.691979170', expected '1699779738.691979170', error '0.000000000'

Test #4:

score: -100
Wrong Answer
time: 37ms
memory: 3840kb

input:

16666
2 -732787031 -732787030
3 -798263477 735869144 -583647039 529057159 -583647039 529057160
3 -777230180 499482549 -777230181 499482549 -777230180 499482548
3 -661853868 251627327 -661853868 251627326 -661853867 251627327
2 463140451 463140452
3 232604219 637008523 797038205 345997813 797038205 3...

output:

0.00000000000
0.00000000000
-1
-1
-1
0.00000000000
-1
-1
-1
0.00000000000
0.00000005960
0.00000000000
0.00000000000
0.00000000000
-1
0.00000000000
0.00000000000
0.00000000000
-1
-1
0.00000000000
0.00000000000
-1
0.00000002980
0.00000005960
0.00000002980
0.00000000000
0.00000000000
0.00000000000
0.00...

result:

wrong answer 1st numbers differ - expected: '-1.0000000', found: '0.0000000', error = '1.0000000'