QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#856190 | #9728. Catch the Star | yylx | WA | 28ms | 3968kb | C++17 | 5.1kb | 2025-01-13 17:55:23 | 2025-01-13 17:55:49 |
Judging History
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;
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 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),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),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),-1));}
else if(l1.h.y==0 && ps2[(r1+1)%n2].y>0) {p.push_back(make_pair(inter(l1,x_axis),-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),1));}
else if(l2.h.y<l2.t.y && l2.t.y<0) {f2=1,p.push_back(make_pair(inter(l2,x_axis),-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]),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]),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]),-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]),-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 a.first!=b.first ? 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("%ld",&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: 3840kb
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: 28ms
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 -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'