The main road in Bytecity is a straight line from south to north. Conveniently, there are coordinates measured in meters from the southernmost building in north direction.
At some points on the road there are n friends, and i-th of them is standing at the point xi meters and can move with any speed no greater than vi meters per second in any of the two directions along the road: south or north.
You are to compute the minimum time needed to gather all the n friends at some point on the road. Note that the point they meet at doesn't need to have integer coordinate.
The first line contains single integer n (2 ≤ n ≤ 60 000) — the number of friends.
The second line contains n integers x1, x2, ..., xn (1 ≤ xi ≤ 109) — the current coordinates of the friends, in meters.
The third line contains n integers v1, v2, ..., vn (1 ≤ vi ≤ 109) — the maximum speeds of the friends, in meters per second.
Print the minimum time (in seconds) needed for all the n friends to meet at some point on the road.
Your answer will be considered correct, if its absolute or relative error isn't greater than 10 - 6. Formally, let your answer be a, while jury's answer be b. Your answer will be considered correct if 
holds.
3
7 1 3
1 2 1
2.000000000000
4
5 10 3 2
2 3 2 4
1.400000000000
In the first sample, all friends can gather at the point 5 within 2 seconds. In order to achieve this, the first friend should go south all the time at his maximum speed, while the second and the third friends should go north at their maximum speeds.
题意：x轴上有n个人 坐标为xi 最大行驶速度为vi 让这n个人走到相同一点的最短时间上多少
三分坐标 每次看到达这个坐标的最大时间 相互比较
#include<iostream>
#include<cstdio>
#include<cmath>
#include<map>
#include<cstdlib>
#include<vector>
#include<set>
#include<queue>
#include<cstring>
#include<string.h>
#include<algorithm>
#define INF 0x3f3f3f3f
typedef long long ll;
typedef unsigned long long LL;
using namespace std;
const double eps=0.0000001;
const int N=+;
double a[N],b[N];
int n;
double fun(double x){
double ans=;
for(int i=;i<n;i++)ans=max(ans,fabs(x-a[i])/b[i]);
return ans;
}
int main(){
while(scanf("%d",&n)!=EOF){
double maxx=-1.0*INF;
double minn=1.0*INF;
for(int i=;i<n;i++){
scanf("%lf",&a[i]);
maxx=max(maxx,a[i]);
minn=min(minn,a[i]);
}
for(int i=;i<n;i++)scanf("%lf",&b[i]);
double high=maxx;
double low=minn;
while(low+eps<high){
double mid=(high+low)/2.0;
double midd=(mid+high)/2.0;
if(fun(mid)<fun(midd))high=midd;
else
low=mid;
}
printf("%.12f\n",fun(low));
}
}
hdu 4355
Party All the Time
Time Limit: 6000/2000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 5384 Accepted Submission(s): 1679
the Dark forest, there is a Fairy kingdom where all the spirits will go
together and Celebrate the harvest every year. But there is one thing
you may not know that they hate walking so much that they would prefer
to stay at home if they need to walk a long way.According to our
observation,a spirit weighing W will increase its unhappyness for S3*W units if it walks a distance of S kilometers.
Now
give you every spirit's weight and location,find the best place to
celebrate the harvest which make the sum of unhappyness of every spirit
the least.
first line of the input is the number T(T<=20), which is the number
of cases followed. The first line of each case consists of one integer
N(1<=N<=50000), indicating the number of spirits. Then comes N
lines in the order that x[i]<=x[i+1] for all i(1<=i<N). The i-th line contains two real number : Xi,Wi, representing the location and the weight of the i-th spirit. ( |xi|<=106, 0<wi<15 )
each test case, please output a line which is "Case #X: Y", X means the
number of the test case and Y means the minimum sum of unhappyness
which is rounded to the nearest integer.
#include<iostream>
#include<cstdio>
#include<cmath>
#include<map>
#include<cstdlib>
#include<vector>
#include<set>
#include<queue>
#include<cstring>
#include<string.h>
#include<algorithm>
#define INF 0x3f3f3f3f
typedef long long ll;
typedef unsigned long long LL;
using namespace std;
const double eps=0.00000001;
const int N=+;
int n;
struct node{
double x;
double w;
}a[N];
double fun(double x){
double ans=0.0;
for(int i=;i<n;i++){
double t=fabs(a[i].x-x);
ans=ans+t*t*t*a[i].w;
}
return ans;
}
int main(){
//cout<<eps<<endl;
int t;
scanf("%d",&t);
for(int k=;k<=t;k++){
scanf("%d",&n);
double minn=1.0*INF;
double maxx=-1.0*INF;
for(int i=;i<n;i++){
scanf("%lf%lf",&a[i].x,&a[i].w);
maxx=max(maxx,a[i].x);
minn=min(minn,a[i].x);
}
double low=minn;
double high=maxx;
double ans=low;
while(low+eps<high){
double mid=(low+high)/2.0;
double midd=(mid+high)/2.0;
// cout<<fun(mid)<<" "<<fun(midd)<<endl;
if(fun(mid)<fun(midd)){
high=midd;
}
else{
low=mid;
ans=low;
} }
printf("Case #%d: %.0f\n",k,fun(ans));
}
}
hdu 2438
Turn the corner
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3181 Accepted Submission(s): 1289
One
day he comes to a vertical corner. The street he is currently in has a
width x, the street he wants to turn to has a width y. The car has a
length l and a width d.
Can Mr. West go across the corner?
Proceed to the end of file.
求f(a)=l*cos(a)-(x-w/cos(a))/tan(a);
#include<iostream>
#include<cstdio>
#include<cmath>
#include<map>
#include<cstdlib>
#include<vector>
#include<set>
#include<queue>
#include<cstring>
#include<string.h>
#include<algorithm>
#define INF 0x3f3f3f3f
typedef long long ll;
typedef unsigned long long LL;
using namespace std;
const double PI=acos(-1.0);
const double eps=0.00000001;
double x,y,l,w;
double fun(double a){
double ans=l*cos(a)-(x-w/cos(a))/tan(a);
return ans;
}
int main(){
while(scanf("%lf%lf%lf%lf",&x,&y,&l,&w)!=EOF){
double low=0.0;
double high=PI/2.0;
if(x<w||y<w)
{
cout<<"no"<<endl;
continue;
}
while(low+eps<high){
double mid=(low+high)/2.0;
double midd=(mid+high)/2.0;
if(fun(mid)<=fun(midd)){
low=mid;
}
else
high=midd;
}
if(fun(low)<=y)cout<<"yes"<<endl;
else
cout<<"no"<<endl;
}
}