QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#879418 | #9728. Catch the Star | ucup-team5008 | WA | 0ms | 4096kb | C++23 | 6.6kb | 2025-02-02 01:41:13 | 2025-02-02 01:41:14 |
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);}
struct line{
Pt a,b,ab;
line()=default;
line(Pt a,Pt b):a(a),b(b),ab(b-a){}
};
array<ll,2> tangent(vt& v, Pt p){
using ld=long long;
array<ll,2> res = { -1, -1 };
ll n = SZ(v);
rep(i,2){
Pt vle = v[1] - v[0], tl = v[0] - p, vv = v[0] - v[n-1], tt = v[n-1] - p;
ld left = cross(tl, vle), prev = cross(tt, vv);
ll l = 0, r = n-1;
if(i == 0 && prev > 0 && left <= 0){
res[0] = 0;
if (left >= 0){
Pt vn = v[2]-v[1];
Pt tn = v[1]-p;
ld nxt = cross(tn, vn);
if (nxt < 0) res[0] = 1;
else return {1, 1};
}
}
else if (i == 1 && prev <= 0 && left > 0){
res[1] = 0;
if (res[0] != n-1 && prev >= 0) res[1] = n-1;
}
else{
while (l < r-1) {
ll m = (r+l+1) / 2;
Pt vm = v[m+1] - v[m];
Pt tm = v[m] - p;
ld mid = cross(tm, vm);
ld lmd = cross(tl, tm);
if (i == 0 &&
((mid <= 0) || (lmd < 0)) &&
((left > 0) || (lmd >= 0))) {
r = m;
}
else if (i == 1 &&
((left <= 0) || (lmd <= 0)) &&
((mid > 0) || (lmd > 0))) {
r = m;
}
else {
l = m;
tl = tm;
left = mid;
}
}
ll next = (r+1)%n;
Pt tr = v[r]-p;
Pt vr = v[next]-v[r];
ld right = cross(tr, vr);
if(i == 0 && right <= 0 && left > 0){
res[0] = r;
Pt vn = v[(next+1)%n] - v[next];
Pt tn = v[next] - p;
ld nxt = cross(tn, vn);
if(right >= 0){
if(nxt < 0) res[0] = next;
else if(nxt <= 0) return {next, next};
}
}
else if(i == 0) return {-1, -1};
else if(right > 0 && left <= 0){
res[1] = r;
if((res[0] != l) && left >= 0) res[1] = l;
}
}
}
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();
return res;
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) return {res};
return {};
}else{
if(i(l.a)>=strict) 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[0],b);
array<Pt,2> A,B;
rep(i,2){
A[i]=ll(2)*a-v[0][A_[1-i]];
B[i]=ll(2)*b-v[0][B_[1-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);
if(!(seg.a==seg.b)){
if(cross(seg.a,seg.b,l.b)==0){
seg.a=l.a=r.a;
l.b=l.a+l.ab;
} else if(cross(seg.b,seg.a,r.b)==0){
seg.b=r.a=l.a;
r.b=r.a+r.ab;
}
}
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,0), c2=cp(line(seg.b,seg.a),0);
if(!(seg.a==seg.b) && !c1.empty() && !c2.empty()) range.eb(c1[0]), type=2;
if(range.empty()) continue;
if(!(seg.a==seg.b) && i(seg.a)==0 && i(seg.b)==0) continue;
if(i(l.a)==0 && i(l.b)==0) continue;
if(i(r.a)==0 && i(r.b)==0) continue;
if(SZ(range)==3){
query.eb(range[0],1);
query.eb(range[2],-1);
continue;
}
if(SZ(range)==2 && range[0]==range[1]){
vt dir;
Pt problem(range[0].b/range[0].a,0);
if(problem==l.a) dir.eb(l.ab);
if(problem==r.a) dir.eb(r.ab);
if(!(seg.a==seg.b)){
if(seg.a==problem) dir.eb(seg.b-seg.a);
if(seg.b==problem) dir.eb(seg.a-seg.b);
}
if(i(dir[0])>i(dir[1])) swap(dir[0],dir[1]);
if(i(dir[0])>=0 || i(dir[1])<=0) continue;
if(cross(dir[0],dir[1])>0){
query.eb(range[0],1);
query.eb(RIGHT,-1);
}else{
query.eb(range[0],-1);
query.eb(LEFT,1);
}
continue;
}
if(SZ(range)==2){
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{
if(i(seg.ab)>0){
if(max(cross(seg.a,seg.b,r.b),cross(seg.a,seg.b,l.b))>0) t2=0;
else t2=1;
}
else{
if(min(cross(seg.a,seg.b,r.b),cross(seg.a,seg.b,l.b))<0) t2=0;
else t2=1;
}
}
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){
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) assert(ans==0);
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: 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.404761904761905 6.000000000000000
result:
ok 2 numbers
Test #2:
score: -100
Wrong Answer
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 -1 1.000000000000000
result:
wrong answer 2nd numbers differ - expected: '0.0000000', found: '-1.0000000', error = '1.0000000'