QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#736001#5448. 另一个欧拉数问题Qingyu0 0ms0kbC++235.5kb2024-11-11 23:27:562024-11-11 23:27:57

Judging History

你现在查看的是最新测评结果

  • [2024-11-11 23:27:57]
  • 评测
  • 测评结果:0
  • 用时:0ms
  • 内存:0kb
  • [2024-11-11 23:27:56]
  • 提交

answer

#include<bits/stdc++.h>
#define L(i, j, k) for(int i = (j); i <= (k); ++i)
#define R(i, j, k) for(int i = (j); i >= (k); --i)
#define sz(a) ((int) (a).size())
#define ll long long 
#define vi vector<int>
#define me(a, x) memset(a, x, sizeof(a))
#define pb emplace_back
#define mkp make_pair
using namespace std;
const int N = 1e6 + 7, mod = 1e9 + 7;
struct vec {
	ll x, y;
	vec(ll X = 0, ll Y = 0) {
		x = X;
		y = Y;
	}
};
vec operator + (vec a, vec b) {
	return vec(a.x + b.x, a.y + b.y);
}
vec operator - (vec a, vec b) {
	return vec(a.x - b.x, a.y - b.y);
}
__int128 operator * (vec a, vec b) {
	return (__int128)a.x * b.x + (__int128)a.y * b.y;
}
int cmp_ct(vec a, vec b, vec c){
	// printf("ct %lld %lld %lld %lld %lld %lld\n",a.x,a.y,b.x,b.y,c.x,c.y);
	vec v1=vec(a.y-b.y,b.x-a.x);
	vec v2=vec(c.x-b.x,c.y-b.y);
	if(v1*v2>0) return 1; //ccw
	else return 0; //cw
}
bool cmp_ct_0(vec a, vec b, vec c){
		// printf("ct %lld %lld %lld %lld %lld %lld\n",a.x,a.y,b.x,b.y,c.x,c.y);
	vec v1=vec(a.y-b.y,b.x-a.x);
	vec v2=vec(c.x-b.x,c.y-b.y);
	if(v1*v2==0) return 1; //ccw
	else return 0; //cw
}
int n;
ll l, r;
vector<vec>getin() {
	int k;
	cin >> k;
	vector<vec>qwq;
	while(k--) {
		ll x, y;
		cin >> x >> y;
		qwq.pb(vec(x, y));
	}
	return qwq;
}
vector<vec>star;
#define db long double
struct fs{
	ll fz,fm;
	fs(ll ffz,ll ffm)
	{
		fz=ffz,fm=ffm;
	}
	db getdouble(){assert(fm!=0);return 1.0L*fz/fm;}
	bool operator<(const fs&t)const
	{
		return (__int128)fz*t.fm<(__int128)fm*t.fz;
	}
	bool operator>(const fs&t)const
	{
		return (__int128)fz*t.fm>(__int128)fm*t.fz;
	}
	bool operator<=(const fs&t)const
	{
		return (__int128)fz*t.fm<=(__int128)fm*t.fz;
	}
	void print()
	{
		printf("%lld %lld ",fz,fm);
	}
};
const fs fs_inf(-2e18,1);
int buc[1<<20];
int invalid_count;
void Main() {
	cin >> n >> l >> r;
	star=getin();
	int sz=star.size();
	reverse(star.begin(),star.end());
	vector<vec> star1;
	for(int i=1; i<sz; ++i) star1.push_back(star[i]);
	star1.push_back(star[0]);
	// printf("%d\n",sz);
	// for(auto i:star)
		// printf("%lld %lld\n",i.x,i.y);
	// star.push_back(star[0]);
	int zak=0;
	vector<pair<fs,int>> sweep;
	const ll inf=2e18;
	L(t, 1, n) {
		fs LL=fs(-inf,1);
		fs RR=fs(inf,1);
		vector<vec> u = getin();
		auto r = star[0];
		for(auto p : u) {
			int sdt=cmp_ct(p,star[sz-1],star[0]);
			if(cmp_ct_0(p,star[sz-1],star[0])) star.swap(star1),sdt=cmp_ct(p,star[sz-1],star[0]);
			// printf("sdt %d\n",sdt);
			int l=1,r=sz-1,ans=0;
			while(l<=r)
			{
				int mid=(l+r)>>1;
				int res=cmp_ct(p,star[mid-1],star[mid]);
				// printf("bin %d %d\n",mid,res);
				if((res==1)==(sdt==1))
				{
					res=cmp_ct(p,star[0],star[mid]);
				}
				if((res==1)==(sdt==1))
				{
					ans=mid,l=mid+1;
				}
				else r=mid-1;
			}
			// printf("try %lld %lld ",p.x,p.y);
			// printf("get %lld %lld ",star[ans].x,star[ans].y);
			int ans1=0;
			l=1,r=sz-1;
			while(l<=r)
			{
				int mid=(l+r)>>1;
				int res=cmp_ct(p,star[mid-1],star[mid]);
				if((res==1)==(sdt==1))
				{
					res=cmp_ct(p,star[0],star[mid]);
				}
				else res=sdt;
				if((res==1)==(sdt==1))
				{
					ans1=mid,l=mid+1;
				}
				else r=mid-1;
			}
			// printf("GET %lld %lld\n",star[ans1].x,star[ans1].y);
			if(cmp_ct(p,star[ans],star[ans1])==0) swap(ans,ans1);
			//p->ans, we want left(ccw)
			auto A=p,B=star[ans];
			++zak;
			fs LLL=fs(-inf,1);
			fs RRR=fs(inf,1);
			auto addseg=[&](){
			if(A.y==B.y)
			{
				if((A.y>0)==(A.x<B.x))
				{
					// sweep.push_back({fs_inf,zak});
					// LLL=max(LLL,)
				}
			}
			else
			{
				//intersect with X-axis
				auto [x1,y1]=A;
				auto [x2,y2]=B;
				// printf("%lld %lld %lld %lld\n",x1,y1,x2,y2);
				swap(x1,y1);
				swap(x2,y2);
				if(x1>x2) swap(x1,x2),swap(y1,y2);
				auto intersect=fs(y1*(x2-x1)-x1*(y2-y1),x2-x1);
				// printf("%lld %lld %lld %lld %lld %lld\n",x1,y1,x2,y2,intersect.fz,intersect.fm);
				if(cmp_ct(A,B,vec(inf,0)))
				{
					if(intersect<RRR) RRR=intersect;
					// sweep.push_back({fs_inf,zak});
					// sweep.push_back({intersect,-zak});
				}
				else
				{
					if(intersect>LLL) LLL=intersect;
					// sweep.push_back({intersect,zak});
				}
			}};
			// printf("%d %lld %lld\n",zak,A.x,A.y);
			// printf("+ %lld %lld\n",B.x,B.y);
			
			addseg();
			A=star[ans1],B=p;
			addseg();
			if(LL>LLL) LL=LLL;
			if(RR<RRR) RR=RRR;
			// printf("+ %lld %lld\n",A.x,A.y);
			//ans1->p, we want left(ccw)
		}
		++zak;
		sweep.push_back({LL,zak});
		sweep.push_back({RR,-zak});
	}
	// return ;
	// for(auto [A,B]:sweep)
	// {
		// A.print();
		// printf(" %d\n",B);
	// }
	sweep.push_back({fs(l,1),0});
	sweep.push_back({fs(r,1),0});
	sort(sweep.begin(),sweep.end());
	fs last=fs(-inf,1);
	bool exist=0;
	db ans=0;
	for(auto [t,id]:sweep)
	{
		//time calc
		
		bool dontcalc=0;
		if(t<=fs(l,1)){last=t;dontcalc=1;}
		if(invalid_count==0&&!dontcalc)
			exist=1,
			// printf("%.3Lf %.3Lf\n",tast.getdouble(),t.getdouble()),
			ans=(ans+t.getdouble()-last.getdouble());


		if(id<0)
		{
			if(buc[-id]--==1) --invalid_count;
		}
		if(id>0)
		{
			if(++buc[id]==1) ++invalid_count;
		}
		// printf("%lld %lld %d %d %.2Lf\n",t.fz,t.fm,id,invalid_count,ans);

		last=t;

		if(t<=fs(r,1)&&fs(r,1)<=t) break;
	}
	if(exist==0) puts("-1");
	else printf("%.15Lf\n",ans);
	for(int i=1; i<=zak; ++i) buc[i]=0;
	invalid_count=0;
	zak=0;
}
int main() {
	ios :: sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int t; cin >> t; while(t--) Main();
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Time Limit Exceeded

Test #1:

score: 0
Time Limit Exceeded

input:

584 1985 1017 186
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 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 ...

output:


result:


Subtask #2:

score: 0
Time Limit Exceeded

Test #11:

score: 0
Time Limit Exceeded

input:

1 199913 100055 1
1

output:


result:


Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Time Limit Exceeded

Test #21:

score: 0
Time Limit Exceeded

input:

2 199984 99989 1
1 1

output:


result:


Subtask #5:

score: 0
Skipped

Dependency #4:

0%

Subtask #6:

score: 0
Skipped

Dependency #1:

0%