QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#857382 | #9728. Catch the Star | yylx | WA | 27ms | 3968kb | C++17 | 5.6kb | 2025-01-15 16:50:51 | 2025-01-15 16:50:58 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
struct point {long long x,y;};
struct line {point h,t;};
long long t,n,l,r,s,cnt,f,F,x,y;
double op;
vector<point> st,ms;
vector<pair<line,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(line a) {return (double)cx(a.h,a.t)/(double)(a.t.y-a.h.y);}
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(ls[i],1));}
else if(ls[i].h.y<ls[i].t.y && ls[i].h.y<0) {f2=1;p.push_back(make_pair(ls[i],-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(ls[i],1));}
else if(ls[i].t.y==0 && ls[i+1].t.y<0) {f1=1;p.push_back(make_pair(ls[i],1));}
}
else if(ls[i].h.y<ls[i].t.y)
{
if(ls[i].t.y>0) {f2=1;p.push_back(make_pair(ls[i],-1));}
else if(ls[i].t.y==0 && ls[i+1].t.y>0) {f2=1;p.push_back(make_pair(ls[i],-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(ls[i],1));}
else if(ls[i].t.y==0 && ls[i+1].t.y<0) {f1=1;p.push_back(make_pair(ls[i],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(ls[i],-1));}
else if(ls[i].t.y==0 && ls[i+1].t.y>0) {f2=1;p.push_back(make_pair(ls[i],-1));}
}
}
}
if(f1==0 && f2==1) p.push_back(make_pair((line){{-1000000001,0},{-1000000001,1}},1));
}
void tangent(vector<point> &ps1,vector<point> &ps2)
{
int n1=ps1.size(),n2=ps2.size(),l,r1,r2,r,nxt;
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]};
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<line,int> p1,pair<line,int> p2)
{
long long a=cx(p1.first.h,p1.first.t),c=cx(p2.first.h,p2.first.t);
int b=p1.first.t.y-p1.first.h.y,d=p2.first.t.y-p2.first.h.y;
long long e=b*d;
long long X=a*d,Y=b*c;
if(X==Y) return p1.second<p2.second;
if(e>0) return X<Y;
return X>Y;
}
bool cmp2(pair<line,int> p1,pair<line,int> p2)
{
double a=cx(p1.first.h,p1.first.t)/(p1.first.t.y-p1.first.h.y),b=cx(p2.first.h,p2.first.t)/(p2.first.t.y-p2.first.h.y);
return a==b ? p1.second<p2.second : a<b;
}
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("%lld",&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((line){{l,0},{l,1}},2));
p.push_back(make_pair((line){{r,0},{r,1}},-2));
sort(p.begin(),p.end(),cmp2);
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 break;
if(f==1 && cnt==0)
{
F=1;
op+=inter(p[i+1].first)-inter(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: 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: 0
Accepted
time: 27ms
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:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 ...
result:
ok 16666 numbers
Test #5:
score: -100
Wrong Answer
time: 26ms
memory: 3968kb
input:
16667 2 -9 7 3 -8 4 -6 1 -4 2 3 6 13 2 12 3 10 3 -1 7 0 10 -3 4 2 -9 5 3 -8 10 -5 8 -4 10 3 10 -8 9 -11 12 -8 3 -10 -5 -8 -4 -7 -1 2 -6 5 3 -8 6 -7 6 -5 7 3 -2 -3 1 -4 -4 -2 3 1 10 0 10 -1 8 2 -9 9 3 -5 -11 -2 -11 -5 -8 3 6 -5 5 -2 4 -5 3 11 6 9 3 11 3 2 -6 5 3 -7 6 -8 7 -9 4 3 9 2 12 -3 11 0 3 -6 3...
output:
16.00000000000 14.00000000000 11.00000000000 15.55555555556 -1 12.00000000000 14.00000000000 17.00000000000 11.00000000000 16.00000000000 11.00000000000 15.00000000000 15.00000000000 10.00000000000 18.00000000000 16.00000000000 14.00000000000 17.00000000000 12.00000000000 16.00000000000 10.000000000...
result:
wrong answer 127th numbers differ - expected: '4.3333333', found: '3.5333333', error = '0.1846154'