QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#759876#9728. Catch the Starucup-team1004WA 34ms3956kbC++174.4kb2024-11-18 12:55:392024-11-18 12:55:40

Judging History

This is the latest submission verdict.

  • [2024-11-18 12:55:40]
  • Judged
  • Verdict: WA
  • Time: 34ms
  • Memory: 3956kb
  • [2024-11-18 12:55:39]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#include"debug.h"
#else
#define debug(...) void()
#endif
#define all(x) (x).begin(),(x).end()
template<class T>
auto ary(T *a,int l,int r){
	return vector<T>{a+l,a+1+r};
}
using ll=long long;
using ull=unsigned long long;
using vec=complex<int>;
using ld=long double;
ll dot(const vec &a,const vec &b){
	return 1ll*real(a)*real(b)+1ll*imag(a)*imag(b);
}
ll cross(const vec &a,const vec &b){
	return dot(a,b*vec(0,-1));
}
struct frac{
	ll x,y;
	frac()=default;
	frac(ll a,ll b=1):x(a),y(b){}
	ld calc()const{
		return (ld)x/y;
	}
};
#ifdef DEBUG
ostream& operator << (ostream &out,frac a){
	return out<<a.calc();
}
#endif
using LL=__int128;
bool operator < (const frac &a,const frac &b){
	return (LL)a.x*b.y<(LL)b.x*a.y;
}
template<class T>
int sign(const T &x){
	return x?(x>0?1:-1):0;
}
int T,n,L,R;
using poly=vector<vec>;
poly a,b;
void read(poly &a){
	int k;
	scanf("%d",&k);
	a.resize(k);
	for(int i=0,x,y;i<k;i++){
		scanf("%d%d",&x,&y);
		a[i]=vec(x,y);
	}
}
pair<int,int> find(vec s,const poly &a){
	int n=a.size(),st=0;
	if(!cross(a[0]-s,a[1]-s))st=1;
	// debug(s,a,st);
	int op=sign(cross(a[st]-s,a[st+1]-s));
	// assert(op!=0);
	int l=0,r=n,mid;
	for(;l+1<r;){
		mid=(l+r)>>1;
		if(sign(cross(a[st]-s,a[(st+mid)%n]-s))==op)l=mid;
		else r=mid;
	}
	// assert(cross(a[st]-s,a[(st+l)%n]-s)*op>0);
	// assert(cross(a[st]-s,a[(st+r)%n]-s)*op<=0);
	// debug(st,st+l,st+r,op);
	auto find=[&](int st,int len,int op){
		int l=0,r=len,mid;
		for(;l<r;){
			mid=(l+r)>>1;
			int u=(st+mid)%n,v=(u+1)%n;
			if(sign(cross(a[u]-s,a[v]-s))==op)l=mid+1;
			else r=mid;
		}
		return (st+l)%n;
	};
	int p=find(st,l,op),q=find((st+r)%n,(n-r)%n,-op);
	return op>0?make_pair(p,q):make_pair(q,p);
}
frac calc(vec a,vec b){
	ll s=cross(b-L,a-L),t=cross(a-R,b-R);
	if(s<0)s=-s,t=-t;
	assert(s>0&&t>0);
	return frac(s,s+t);
}
vector<pair<frac,int>>c;
bool solve(){
	int n=b.size();
	auto [s,t]=find(a[0],b);
	int x=[&](){
		int l=0,r=(t-s+n)%n,mid;
		for(;l<r;){
			mid=(l+r)>>1;
			int u=(s+mid)%n,v=(u+1)%n;
			if(cross(b[v]-b[u],a[find(b[u],a).first]-b[u])>0)l=mid+1;
			else r=mid;
		}
		return (s+l)%n;
	}();
	int y=[&](){
		int l=0,r=(t-s+n)%n,mid;
		for(;l<r;){
			mid=(l+r)>>1;
			int u=(t-mid+n)%n,v=(u+n-1)%n;
			if(cross(a[find(b[u],a).second]-b[u],b[v]-b[u])>0)l=mid+1;
			else r=mid;
		}
		return (t-l+n)%n;
	}();
	int p=find(b[x],a).first;
	int q=find(b[y],a).second;
	for(vec t:a)assert(cross(a[p]-b[x],t-b[x])<=0);
	for(vec t:a)assert(cross(a[q]-b[y],t-b[y])>=0);
	for(vec t:b)assert(cross(b[x]-a[p],t-a[p])<=0);
	for(vec t:b)assert(cross(b[y]-a[q],t-a[q])>=0);
	// debug(b,p,x,q,y);
	auto chkin=[&](vec u,int o1,int o2){
		return
			cross(a[p]-b[x],u-b[x])>=o1&&
			cross(b[y]-b[x],u-b[x])>0&&
			cross(u-b[y],a[q]-b[y])>=o2;
	};
	if(chkin(L,1,0)&&chkin(R,0,1))return 0;
	if(chkin(R,1,0)&&chkin(L,0,1))return 0;
	auto check=[&](vec s,vec t){
		ll p=cross(R-L,t-L),q=cross(R-L,s-L);
		if(sign(p)*sign(q)<=0||abs(p)>=abs(q))return false;
		return sign(cross(t-s,L-s))*sign(cross(t-s,R-s))<0;
	};
	int o1=check(a[p],b[x]),o2=check(a[q],b[y]);
	if(o1&&o2){
		frac s=calc(a[p],b[x]),t=calc(a[q],b[y]);
		if(t<s)swap(s,t);
		c.push_back({s,1});
		c.push_back({t,-1});
	}else if(o1){
		frac s=calc(a[p],b[x]);
		if(cross(a[p]-b[x],L-b[x])>0){
			c.push_back({frac(0),1});
			c.push_back({s,-1});
		}else{
			c.push_back({s,1});
			c.push_back({frac(1),-1});
		}
	}else if(o2){
		frac s=calc(a[q],b[y]);
		if(cross(L-b[y],a[q]-b[y])>0){
			c.push_back({frac(0),1});
			c.push_back({s,-1});
		}else{
			c.push_back({s,1});
			c.push_back({frac(1),-1});
		}
	}
	return 1;
}
void work(){
	scanf("%d%d%d",&n,&L,&R);
	read(a);
	c.clear();
	ld ans=0;
	bool flag=0;
	for(int i=1;i<=n;i++){
		read(b);
		if(!solve())flag=1;
	}
	if(flag)return puts("-1"),void();
	// debug(c);
	c.push_back({frac(0),0});
	c.push_back({frac(1),0});
	sort(all(c));
	for(int i=0,x=0;i+1<c.size();i++){
		x+=c[i].second;
		if(!x){
			ans+=c[i+1].first.calc()-c[i].first.calc();
			if(frac(0)<c[i].first&&c[i].first<frac(1))flag=1;
			if(c[i].first<c[i+1].first)flag=1;
		}
	}
	ans*=abs(R-L);
	if(flag)printf("%.15Lf\n",ans);
	else puts("-1");
}
int main(){
	for(scanf("%d",&T);T--;)work();
	return 0;
}
#ifdef DEBUG
#include"debug.hpp"
#endif

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3904kb

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: 3912kb

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: 3956kb

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: 34ms
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: 33ms
memory: 3912kb

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 815th numbers differ - expected: '-1.0000000', found: '17.0000000', error = '18.0000000'