QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#879251#9728. Catch the Starucup-team5008WA 47ms4096kbC++206.8kb2025-02-01 22:49:222025-02-01 22:49:23

Judging History

This is the latest submission verdict.

  • [2025-02-01 22:49:23]
  • Judged
  • Verdict: WA
  • Time: 47ms
  • Memory: 4096kb
  • [2025-02-01 22:49:22]
  • Submitted

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={-1,-1};
	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) 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_[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]), assert(cross(b,B[0],a)>=0);
			if(cross(a,A[1],b)<=0) l=line(a,A[1]);
			else l=line(b,B[1]), assert(cross(b,B[1],a)<=0);
			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,0), c2=cp(line(r.a,l.a),0);
			if(!(seg.a==seg.b) && !c1.empty() && !c2.empty()) range.eb(c1[0]), type=2, assert(c1[0]==c2[0]);
			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;
			sort(all(range));
			assert(SZ(range)<4);
			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);
				}
				assert(SZ(dir)==2);
				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){
				if(!(range[0]<range[1])) swap(range[0],range[1]);
//				if(range[0] == range[1]) continue;
//				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(min(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<<" "<<type<<" "<<t2<<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: 1ms
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: 46ms
memory: 3584kb

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: 47ms
memory: 4096kb

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
11.000000000000000
16.000000000000000
11.000000000000000
15.000000000000000
15.000000000000000
10.000000000000000
18.000000000000000
16.000000000000000
14.000000000...

result:

wrong answer 191st numbers differ - expected: '16.0000000', found: '-1.0000000', error = '1.0625000'