QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#925218 | #2582. 物理实验 | ANIG | 100 ✓ | 1038ms | 6504kb | C++14 | 2.6kb | 2025-03-04 11:12:41 | 2025-03-04 11:12:42 |
Judging History
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