QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#856204#9728. Catch the StaryylxWA 30ms3968kbC++175.6kb2025-01-13 18:32:022025-01-13 18:32:04

Judging History

This is the latest submission verdict.

  • [2025-01-13 18:32:04]
  • Judged
  • Verdict: WA
  • Time: 30ms
  • Memory: 3968kb
  • [2025-01-13 18:32:02]
  • Submitted

answer

#include <bits/stdc++.h>

using namespace std;

struct point {long long 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;

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

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};}

long long dot(point a,point b) {return a.x*b.x+a.y*b.y;}    
long long cx(point a,point b) {return a.x*b.y-a.y*b.x;}         
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_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);} 

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

void inter(vector<line> &ls)
{
    int f1=0,f2=0;
    for(int i=0;i<ls.size();i+=1)
    {
        if(i==ls.size()-1)
        {
            if(ls[i].h.y>ls[i].t.y && ls[i].h.y>0) {f1=1;p.push_back(make_pair(inter(ls[i],x_axis),1));}
            else if(ls[i].h.y<ls[i].t.y && ls[i].h.y<0) {f2=1;p.push_back(make_pair(inter(ls[i],x_axis),-1));}
        }
        else if(i==0)
        {
            if(ls[i].h.y>ls[i].t.y)
            {
                if(ls[i].t.y<0) {f1=1;p.push_back(make_pair(inter(ls[i],x_axis),1));}
                else if(ls[i].t.y==0 && ls[i+1].t.y<0) {f1=1;p.push_back(make_pair(inter(ls[i],x_axis),1));}
            }
            else if(ls[i].h.y<ls[i].t.y)
            {
                if(ls[i].t.y>0) {f2=1;p.push_back(make_pair(inter(ls[i],x_axis),-1));}
                else if(ls[i].t.y==0 && ls[i+1].t.y>0) {f2=1;p.push_back(make_pair(inter(ls[i],x_axis),-1));}
            }
        }
        else
        {
            if(ls[i].h.y>ls[i].t.y && ls[i].h.y>0)
            {
                if(ls[i].t.y<0) {f1=1;p.push_back(make_pair(inter(ls[i],x_axis),1));}
                else if(ls[i].t.y==0 && ls[i+1].t.y<0) {f1=1;p.push_back(make_pair(inter(ls[i],x_axis),1));}
            }
            else if(ls[i].h.y<ls[i].t.y && ls[i].h.y<0)
            {
                if(ls[i].t.y>0) {f2=1;p.push_back(make_pair(inter(ls[i],x_axis),-1));}
                else if(ls[i].t.y==0 && ls[i+1].t.y>0) {f2=1;p.push_back(make_pair(inter(ls[i],x_axis),-1));}
            }
        }
    }
    if(f1!=f2)
    {
        if(f1==0) p.push_back(make_pair(-1e9-1,1));
        else p.push_back(make_pair(1e9+1,-1));
    }
}

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;
    ls.clear();
    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={ps2[r],ps2[r]+ps2[r]-ps1[l]};
    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]-ps2[r]),ps2[r]};
    ls.push_back(l1);
    for(int i=r1;i!=r2;i=nxt)
    {
        nxt=(i+1)%n2;
        ls.push_back({ps2[i],ps2[nxt]});
    }
    ls.push_back(l2);
    inter(ls);
}

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("%lld%lld%lld",&n,&l,&r);
    st.clear();
    op=0;
    cnt=0;
    f=0;
    F=0;
    p.clear();
    scanf("%lld",&s);
    for(int i=0;i<s;i+=1)
    {
        scanf("%lld%lld",&x,&y);
        st.push_back({x,y});
    }
    for(int j=0;j<n;j+=1)
    {
        ms.clear();
        scanf("%ld",&s);
        for(int i=0;i<s;i+=1)
        {
            scanf("%lld%lld",&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("%lld",&t);
    while(t--) solve();
    return 0;
}

详细

Test #1:

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

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: 3968kb

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: 30ms
memory: 3968kb

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
0.00000000000
0.00000000000
0.00000000000
0.00000000000
0.00000000000
0.00000002980
-1
0.00000000000
0.00000000000
0.00000000000
0.00000000000
0.00000000000
0.00000000000
0.00000000000
-1
0.00000000000
-1
0.00000000000
0.00000000000
0.00000000000
-1
0.00000001490
0.000000...

result:

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