QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#925218#2582. 物理实验ANIG100 ✓1038ms6504kbC++142.6kb2025-03-04 11:12:412025-03-04 11:12:42

Judging History

This is the latest submission verdict.

  • [2025-03-04 11:12:42]
  • Judged
  • Verdict: 100
  • Time: 1038ms
  • Memory: 6504kb
  • [2025-03-04 11:12:41]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e4+5;
const double pi=acos(-1),eps=1e-12;
struct node{
	double x,y;
	friend node operator-(node a,node b){
		return {a.x-b.x,a.y-b.y};
	}
	friend node operator*(double a,node b){
		return {a*b.x,a*b.y};
	}
	friend node operator+(node a,node b){
		return {a.x+b.x,a.y+b.y};
	}
}p1[N],p2[N],st,ed;
double nw,f1[N],f2[N];
struct msg{
	double x;
	int bh,op;
	friend bool operator<(msg a,msg b){
		return a.x<b.x;
	}
};
node gets(node a,node b){
	return a+((nw-a.y)/(b.y-a.y))*(b-a);
}
struct nds{
	node a,b;
	friend bool operator<(nds a,nds b){
		return abs(gets(a.a,a.b).x)<abs(gets(b.a,b.b).x)-eps;
	}
};
double jd1(nds x){
	node a=x.a,b=x.b,t=b-a;
	return pi/2-atan2(t.y,t.x);
}
double jd2(nds x){
	node a=x.a,b=x.b,t=b-a;
	return atan2(t.y,t.x)-pi/2;
}
node rot(node a,double x){
	return {a.x*cos(x)-a.y*sin(x),a.x*sin(x)+a.y*cos(x)};
}
double k;
int t,n;
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>t;
	while(t--){
		memset(f1,0,sizeof(f1));
		memset(f2,0,sizeof(f2));
		cin>>n;
		for(int i=1;i<=n;i++){
			cin>>p1[i].x>>p1[i].y>>p2[i].x>>p2[i].y;
		}
		cin>>st.x>>st.y>>ed.x>>ed.y>>k;
		node to=ed-st;
		double tmp=atan2(to.y,to.x)-pi/2;
		tmp=2*pi-tmp;
		st=rot(st,tmp);ed=rot(ed,tmp);
		vector<msg>q;
		for(int i=1;i<=n;i++){
			p1[i]=rot(p1[i],tmp);
			p2[i]=rot(p2[i],tmp);
			p1[i]=p1[i]-st;
			p2[i]=p2[i]-st;
			if(p1[i].y>p2[i].y)swap(p1[i],p2[i]);
			q.push_back({p1[i].y,i,0});
			q.push_back({p2[i].y,i,1});
		//	cout<<p1[i].x<<" "<<p1[i].y<<" "<<p2[i].x<<" "<<p2[i].y<<endl;
		}
		set<nds>jl1,jl2;
		sort(q.begin(),q.end());
		for(int i=0;i<q.size();i++){
			double x=q[i].x;
			int bh=q[i].bh,op=q[i].op;
			if(jl1.size())f1[i]=1/cos(jd1(*jl1.begin()));
			if(jl2.size())f2[i]=1/cos(jd2(*jl2.begin()));
			nw=x;
			if(op==0){
				if(p1[bh].x>0)jl1.insert({p1[bh],p2[bh]});
				else jl2.insert({p1[bh],p2[bh]});
			}else{
				if(p1[bh].x>0)jl1.erase(jl1.find({p1[bh],p2[bh]}));
				else jl2.erase(jl2.find({p1[bh],p2[bh]}));
			}
		}
		int lst=0;
		double ans=0,res=0;
		for(int i=1;i<q.size();i++){
			ans+=(q[i].x-q[i-1].x)*(f1[i]+f2[i]);
			while(q[i].x-q[lst].x>k)lst++,ans-=(q[lst].x-q[lst-1].x)*(f1[lst]+f2[lst]);
			res=max(res,ans+(k-(q[i].x-q[lst].x))*(f1[lst]+f2[lst]));
		}
		lst=q.size()-1;
		ans=0;
		for(int i=q.size()-2;i>=0;i--){
			ans+=(q[i+1].x-q[i].x)*(f1[i+1]+f2[i+1]);
			while(q[lst].x-q[i].x>k)ans-=(q[lst].x-q[lst-1].x)*(f1[lst]+f2[lst]),lst--;
			res=max(res,ans+(k-(q[lst].x-q[i].x))*(f1[lst+1]+f2[lst+1]));
		}
		printf("%.10lf\n",res);
	}
}

Details

Tip: Click on the bar to expand more detailed information

Pretests


Final Tests

Test #1:

score: 40
Accepted
time: 9ms
memory: 4352kb

input:

100
100
7143 -4407 6148 -4332
-3698 1987 -3674 2827
-2240 -6374 -3784 -6054
149 599 327 597
-2580 -4497 -2820 -4347
9219 -1818 6904 502
-5893 1341 -4357 -1890
-3503 -3287 -1087 -1211
-1579 7118 -229 7556
6456 502 1926 -1748
540 6714 -528 6825
1561 8432 -701 8357
422 6998 -41 7462
-1793 3676 1602 517...

output:

939.7746773737
454.2962581289
270.0970128690
17826.6786238372
693.6338490484
649.8851852460
16035.0018585042
1046.5194485707
1243.7315426742
620.6825537524
1320.0566275082
19054.0406513415
1062.0222738142
684.4295601859
421.1793537617
1051.7111712395
850.6338037141
22608.7457029565
13436.1931537422
...

result:

ok ok, 100 numbers

Test #2:

score: 40
Accepted
time: 981ms
memory: 6500kb

input:

100
10000
954303 48690 -14339 924721
464270 12166 -1609 433494
873644 42682 -12246 843861
449837 10414 -1919 418980
537496 14550 -6578 506603
552080 15962 -6594 521226
870138 42252 -12332 840332
57161 -702218 -671596 -43163
38907 -433607 -402515 -34409
445719 9913 -1981 414808
399734 5765 -1530 3686...

output:

23150.5368732009
1591692.1833796101
21928.6043845338
2894.6608545557
14332.0000008225
10772.2001200397
61378.5752462001
113952.2762085166
34711.4113561912
54764.0787161393
76852.1224785756
87090.6178374881
5004.1045959033
79872.5168546938
69493.4970644449
90559.4047765716
86547.5955539103
17134.6650...

result:

ok ok, 100 numbers

Test #3:

score: 20
Accepted
time: 1038ms
memory: 6504kb

input:

100
10000
-636684471 -90006000 664665488 86376811
-263230447 -307903883 362658164 -223073366
-575841687 -121133860 614287459 40176834
-258935135 -268238570 347975250 -185982857
-287828480 -521064727 443096738 -422002609
-315452625 -391084040 435133968 -289354496
-560776752 -215271244 624810954 -5458...

output:

13997587.6583819333
17046702.4199334532
46390075.5222901851
7797517.4204758899
24229463.2094078697
13387746.9424728602
11290240.3043025192
55253758.7425345927
60559802.1793476492
80996320.5440258682
16696606.0002888180
18751679.4997103848
76860841.8119299114
22030848.0532682650
68197919.1737859100
2...

result:

ok ok, 100 numbers