QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#879418#9728. Catch the Starucup-team5008WA 0ms4096kbC++236.6kb2025-02-02 01:41:132025-02-02 01:41:14

Judging History

This is the latest submission verdict.

  • [2025-02-02 01:41:14]
  • Judged
  • Verdict: WA
  • Time: 0ms
  • Memory: 4096kb
  • [2025-02-02 01:41:13]
  • 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);}

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'