• 欢迎光临~

# P5485 [JLOI2010]铁人双项比赛

https://www.luogu.com.cn/problem/P5485

``````#include <bits/stdc++.h>
#define int long long
#define db double
#define pb push_back
using namespace std;
const int N=105;
const db eps=1e-8;
db s,v1[N],v2[N],x[N],b[N],X[N],B[N];
int n;

bool check(db lim) {
bool fl1=0,fl2=0;
db mi=0,mx=0;
for(int i=1;i<n;i++) {
if(fabs(X[i])<eps) {
if(B[i]<lim) return 0;
}
db qwq=1.0*(lim-B[i])/X[i];
//		cout<<i<<" "<<lim<<" "<<(lim-B[i])<<" "<<X[i]<<" "<<(lim-B[i])/X[i]<<'n';
if(X[i]<0&&qwq<=0) {
return 0;
}
if(X[i]<0) {
if(fl2) mi=min(mi,qwq);
else fl2=1,mi=qwq;
} else {
if(fl1) mx=max(mx,qwq);
else fl1=1,mx=qwq;
}
}
if(!fl1||!fl2) return 1;
return mi>=mx;
}

void PR(db k) {
for(int i=1;i<n;i++) {
cout<<(1.0*X[i]*k+B[i])<<'n';
}
db res1=1.0*x[n]*k+b[n];
for(int i=1;i<n;i++) {
db res=1.0*x[i]*k+b[i];
cout<<(res-res1)*3600.0<<'n';
}
db qwq1=k/v1[n]+(s-k)/v2[n];
for(int i=1;i<n;i++) {
db qwq=k/v1[i]+(s-k)/v2[i];
cout<<(qwq-qwq1)*3600.0<<'n';
}
}

db get(db lim) {
bool fl1=0,fl2=0;
db mi=0,mx=0;
for(int i=1;i<n;i++) {
if(fabs(X[i])<eps) {
return 0.0;
}
db qwq=1.0*(lim-B[i])/X[i];
//		cout<<i<<" "<<lim<<" "<<(lim-B[i])<<" "<<X[i]<<" "<<(lim-B[i])/X[i]<<'n';
if(X[i]<0&&qwq<=0) {
return 0;
}
if(X[i]<0) {
if(fl2) mi=min(mi,qwq);
else fl2=1,mi=qwq;
} else {
if(fl1) mx=max(mx,qwq);
else fl1=1,mx=qwq;
}
}
return max(0.0,mx);
}

signed main() {
//	cin.tie(0); ios::sync_with_stdio(false);
cin>>s>>n;
for(int i=1;i<=n;i++) {
cin>>v1[i]>>v2[i];
db qwq=v1[i]*v2[i];
x[i]=(v2[i]-v1[i])/qwq;
b[i]=(s*v1[i])/qwq;
}
for(int i=1;i<n;i++) {
X[i]=1.0*x[i]-1.0*x[n]; B[i]=1.0*b[i]-1.0*b[n];
}
//	PR(14.29);
db l=0,r=1e6;
while(l+eps<r) {
db mid=(l+r)/2.0;
if(check(mid)) l=mid;
else r=mid;
}
bool ok=check(l);
if(ok) {
db k=get(l);
if(k>s) {
cout<<"NO";
return 0;
}
printf("%.2lf %.2lf %lld",k,s-k,(int)floor(l*3600.0+0.5));
} else cout<<"NO";
return 0;
}

``````