QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#879114 | #9728. Catch the Star | ucup-team5008 | WA | 45ms | 4096kb | C++20 | 5.8kb | 2025-02-01 21:18:13 | 2025-02-01 21:18:17 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define rep2(i,j,k) for(ll i=ll(j);i<ll(k);i++)
#define rep(i,k) rep2(i,0,k)
#define rrep2(i,j,k) for(ll i=ll(j)-1;i>=ll(k);i--)
#define rrep(i,j) rrep2(i,j,0)
#define all(a) a.begin(),a.end()
#define SZ(a) ll(a.size())
#define eb emplace_back
using ll=long long;
using vl=vector<ll>;
using vvl=vector<vl>;
using P=pair<ll,ll>;
using vp=vector<P>;
using vvp=vector<vp>;
const ll inf=LLONG_MAX/4;
template<class T>
bool chmin(T& a,T b){return a>b?a=b,1:0;}
template<class T>
bool chmax(T& a,T b){return a<b?a=b,1:0;}
using Pt=complex<ll>;
using vt=vector<Pt>;
#define ln "\n"
#define r(a) real(a)
#define i(a) imag(a)
ll dot(Pt a,Pt b){return r(a)*r(b)+i(a)*i(b);}
ll cross(Pt a,Pt b){return r(a)*i(b)-i(a)*r(b);}
ll cross(Pt a,Pt b,Pt c){return cross(b-a,c-a);}
Pt normal(Pt a){return a*Pt(0,1);}
ll sgn(ll v){return (v>0)-(0>v);}
#define cmp(i,j) sgn(cross(normal(dir),poly[(i)%n]-poly[(j)%n]))
#define extr(i) cmp(i+1,i)>=0 && cmp(i,i-1+n)<0
ll extrVertex(vt &poly,Pt dir){
ll n=SZ(poly), lo=0, hi=n;
if(extr(0)) return 0;
while(lo+1<hi){
ll m=(lo+hi)/2;
if(extr(m)) return m;
ll ls=cmp(lo+1,lo), ms=cmp(m+1,m);
(ls<ms || (ls==ms && ls==cmp(lo,m)) ? hi : lo) = m;
}
return lo;
}
struct line{
Pt a,b,ab;
line()=default;
line(Pt a,Pt b):a(a),b(b),ab(b-a){}
};
#define cmpL(i) sgn(cross(l.a,poly[i],l.b))
array<ll,2> cpf(vt &poly,line l){
ll endA=extrVertex(poly,normal(-l.ab));
ll endB=extrVertex(poly,normal(l.ab));
if(cmpL(endA)<0 || cmpL(endB)>0) return {-1,-1};
array<ll,2> res;
rep(i,2){
ll lo=endB, hi=endA, n=SZ(poly);
while((lo+1)%n!= hi){
ll m=((lo+hi+(lo<hi?0:n))/2)%n;
(cmpL(m)==cmpL(endB) ? lo:hi)=m;
}
res[i]=(lo+!cmpL(hi))%n;
swap(endA,endB);
}
if(res[0]==res[1]) return {res[0],-1};
if(!cmpL(res[0]) && !cmpL(res[1])){
switch((res[0]-res[1]+SZ(poly)+1)%SZ(poly)){
case 0: return {res[0],res[0]};
case 2: return {res[1],res[1]};
}
}
return res;
}
array<ll,2> tangent(vt &poly, Pt p){
#define ccw(i) sgn(cross(p,poly[(i)%n],poly[((i)+1)%n]))
#define rT(i) ccw(i+n-1)<=0 && ccw(i)>=0
#define lT(i) ccw(i+n-1)>=0 && ccw(i)<=0
ll n=SZ(poly);
array<ll,2> res;
if(n<=4){
rep(i,n){
if(rT(i)) res[0]=i;
if(lT(i)) res[1]=i;
}
return res;
}
ll A,B;
rep(s,n){
auto cp=cpf(poly,line(p,poly[s]));
if(cp[1]==-1 || cp[0]==cp[1]) continue;
A=cp[0], B=cp[1];
break;
}
rep(i,2){
ll left=A, right=B;
if(A>B) right+=n;
// rep2(j,left,right+1) cout<<ccw(j)<<" ";
// cout<<endl;
while(left+1<right){
ll mid=(left+right)/2;
if(i==0){
if(ccw(mid)>0) right=mid;
else left=mid;
}
else{
if(ccw(mid)<0) right=mid;
else left=mid;
}
}
res[i]=right%n;
swap(A,B);
}
assert(rT(res[0]) && lT(res[1]));
return res;
}
using ld=long double;
using lint=__int128_t;
struct frac{
ll a,b;
frac(ll _b,ll _a){
a=_a, b=_b;
if(a<0) a=-a, b=-b;
}
friend bool operator<(frac p, frac q){
return lint(p.b)*q.a < lint(p.a)*q.b;
}
ld getVal(){
return b/ld(a);
}
bool operator==(frac p){
return lint(a)*p.b==lint(b)*p.a;
}
};
Pt input(){
ll x,y;cin>>x>>y; return Pt(x,y);
}
vt inV(ll n){
vt res(n);
rep(i,n) res[i]=input();
vt ans;
rep(i,n){
if(cross(res[i],res[(i+1)%n],res[(i+n-1)%n]) != 0) ans.eb(res[i]);
}
return ans;
}
using vi=vector<pair<frac,ll>>;
vector<frac> cp(line l, ll strict=0){
if(i(l.a-l.b) == 0) return {};
frac res(r(l.a)*(-i(l.b))+r(l.b)*i(l.a),i(l.a)-i(l.b));
if(i(l.a)<i(l.b)){
if(i(l.a)<=-strict*2) return {res};
return {};
}else{
if(i(l.a)>=strict*2) return {res};
return {};
}
}
const frac LEFT=frac(-ll(1e9)-10,1), RIGHT=frac(ll(1e9)+10,1);
void solve(){
ll t;cin>>t;
ll L,R; cin>>L>>R;
t++;
vl n(t);
vector<vt> v(t);
rep(i,t){
cin>>n[i];
v[i]=inV(n[i]);
n[i]=SZ(v[i]);
}
vi query;
rep2(i,1,t){
rep(j,n[i]){
Pt a=v[i][j], b=v[i][(j+1)%n[i]];
auto A_=tangent(v[0],a), B_=tangent(v[1],b);
array<Pt,2> A,B;
rep(i,2){
A[i]=ll(2)*a-v[0][A_[i]];
B[i]=ll(2)*b-v[0][B_[i]];
}
line r, l, seg;
if(cross(a,A[0],b)>=0) r=line(a,A[0]);
else r=line(b,B[0]);
if(cross(a,A[1],b)<=0) l=line(a,A[1]);
else l=line(b,B[1]);
seg=line(l.a,r.a);
vector<frac> cand=cp(l);
vector<frac> range;
ll type=-1;
if(!cand.empty()) range.eb(cand[0]), type=0;
cand=cp(r);
if(!cand.empty()) range.eb(cand[0]), type=1;
auto c1=cp(seg,1), c2=cp(line(r.a,l.a),1);
if(!c1.empty() && !c2.empty()) range.eb(c1[0]), type=2;
if(range.empty()) continue;
if(SZ(range)==2){
if(!(range[0]<range[1])) swap(range[0],range[1]);
// cout<<i<<" "<<j<<" "<<range[0].a<<" "<<range[0].b<<" "<<range[1].a<<" "<<range[1].b<<ln;
query.eb(range[0],1);
query.eb(range[1],-1);
continue;
}
ll t2=-1;
if(type==0){
if(i(l.ab)<0) t2=0;
else t2=1;
}else if(type==1){
if(i(r.ab)>0) t2=0;
else t2=1;
}else{
assert(i(seg.ab)!=0);
if(i(seg.ab)>0){
if(max(cross(seg.a,seg.b,r.ab),cross(seg.a,seg.b,l.ab))>0) t2=0;
else t2=1;
}
else{
if(max(cross(seg.a,seg.b,r.ab),cross(seg.a,seg.b,l.ab))<0) t2=0;
else t2=1;
}
}
// cout<<i<<" "<<j<<" "<<range[0].a<<" "<<range[0].b<<ln;
if(t2){
query.eb(range[0],1);
query.eb(RIGHT,-1);
}
else{
query.eb(range[0],-1);
query.eb(LEFT,1);
}
}
}
query.eb(frac(L,1),0);
query.eb(frac(R,1),0);
sort(all(query));
frac last=LEFT;
ll cnt=0;
ld ans=0;
bool flag=false;
for(auto [x, v]: query){
// cout<<x.b<<" "<<x.a<<" "<<v<<ln;
if(cnt==0){
frac lef=last, rig=x;
if(lef<frac(L,1)) lef=frac(L,1);
if(frac(R,1)<rig) rig=frac(R,1);
if(lef==rig){
if(!(lef==frac(L,1)) && !(lef==frac(R,1))) flag=true;
}
else if(lef<rig){
ans+=rig.getVal()-lef.getVal();
flag=true;
}
}
cnt+=v;
last=x;
}
if(flag) cout<<ans<<ln;
else cout<<-1<<ln;
}
int main(){
cin.tie(0)->sync_with_stdio(0);
cout<<fixed<<setprecision(15);
ll t;cin>>t;
while(t--) solve();
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 4096kb
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.404761904761905 6.000000000000000
result:
ok 2 numbers
Test #2:
score: 0
Accepted
time: 0ms
memory: 4096kb
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.000000000000000 1.000000000000000
result:
ok 3 numbers
Test #3:
score: 0
Accepted
time: 0ms
memory: 4096kb
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.691979192313738
result:
ok found '1699779738.691979170', expected '1699779738.691979170', error '0.000000000'
Test #4:
score: 0
Accepted
time: 45ms
memory: 3712kb
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: 45ms
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.000000000000000 14.000000000000000 11.000000000000000 15.555555555555556 -1 12.000000000000000 14.000000000000000 17.000000000000000 -1 16.000000000000000 11.000000000000000 15.000000000000000 15.000000000000000 -1 18.000000000000000 16.000000000000000 14.000000000000000 17.000000000000000 12.000...
result:
wrong answer 9th numbers differ - expected: '11.0000000', found: '-1.0000000', error = '1.0909091'