ZOJ 3421 ZOJ 4041【三分】

ZOJ 3421 - Error Curves

题意 ：给出n条一次或二次函数，x的范围是[0,1000]，让我们求每个x值对应的函数值的最大值的最小值。

题解 ：三分x，对于每一个x找出最大的f(x),然后三分找最小值。

#include<bits/stdc++.h> // #include<cstdio> // #include<vector> // #include<queue> // #include<algorithm> // #include<iostream> // #include<cstring> // #include<string> // #include<cmath> using namespace std; const double pi = acos((double)(-1)); #define inf 0x3f3f3f3f #define ll long long #define eps 1e-10 const int maxn = 20010; const int mod = 1e9 + 7; int t,n; double a[maxn],b[maxn],c[maxn],l,r,midl,midr,ans; double f(double x){ double maxx = a[1]*x*x + b[1]*x + c[1]; for(int i = 2; i <= n;i++){ ans = a[i]*x*x + b[i]*x + c[i]; if(ans > maxx) maxx = ans; } return maxx; } double sanfen(){ l = 0.0, r= 1000.0; while(r - l >eps){ midl = l + (r - l)/3.0; midr = r - (r - l)/3.0; if(f(midl) > f(midr)) l = midl; else r = midr; } return f(r); } int main(){ ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); cin>>t; while(t--){ cin>>n; for(int i = 1;i <= n;i++){ cin>>a[i]>>b[i]>>c[i]; } cout<<fixed<<setprecision(4)<<sanfen()<<endl; } return 0; }

ZOJ 4041 - Chasing

题意 ：有两个点，他们的横坐标都小于0，第二个点的移动速度是第一个点的k倍。问第二个点能否总是在第一个到达y轴前抓到它。

题解：三分第一个点逃离的y值，然后计算两个点到该点的距离比，和他们的速度比进行比较。

#include<bits/stdc++.h> // #include<cstdio> // #include<vector> // #include<queue> // #include<algorithm> // #include<iostream> // #include<cstring> // #include<string> // #include<cmath> using namespace std; const double pi = acos((double)(-1)); #define inf 0x3f3f3f3f #define ll long long #define eps 1e-9 const int maxn = 20010; const int mod = 1e9 + 7; int t; double xa, xb, ya, yb, k,midl,midr,l,r; double getDist(double X1, double Y1, double X2, double Y2){ return sqrt((X1 - X2)*(X1 - X2) + (Y1 - Y2)*(Y1 - Y2)); } double f(double y){ double d1 = getDist(xa, ya, 0, y); double d2 = getDist(xb, yb, 0, y); return d2/d1; } double sanfen(){ l = -100000.0, r = 100000.0; while(r - l>eps){ midl = l + (r - l)/3.0; midr = r - (r - l)/3.0; if(f(midl) > f(midr)) r = midr; else l = midl; } return f(l); } int main(){ ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); cin>>t; while(t--){ cin>>xa>>ya>>xb>>yb>>k; if(k < 1.0) cout<<"N"<<endl; else{ double result = sanfen(); if(result >= k) cout<<"N"<<endl; else cout<<"Y"<<endl; } } return 0; }