首页 > 代码库 > codeforces 782B The Meeting Place Cannot Be Changed+hdu 4355+hdu 2438 （三分）

codeforces 782B The Meeting Place Cannot Be Changed+hdu 4355+hdu 2438 （三分）

2024-09-07 05:54:27   218人阅读

                                                               B. The Meeting Place Cannot Be Changed

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.

Input

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.

Output

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.

Examples
Input
3
7 1 3
1 2 1
Output
2.000000000000
Input
4
5 10 3 2
2 3 2 4
Output
1.400000000000
Note

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个人走到相同一点的最短时间上多少

三分坐标  每次看到达这个坐标的最大时间 相互比较 

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 #include<map>
 5 #include<cstdlib>
 6 #include<vector>
 7 #include<set>
 8 #include<queue>
 9 #include<cstring>
10 #include<string.h>
11 #include<algorithm>
12 #define INF 0x3f3f3f3f
13 typedef long long ll;
14 typedef unsigned long long LL;
15 using namespace std;
16 const double eps=0.0000001;
17 const int N=60000+100;
18 double a[N],b[N];
19 int n;
20 double fun(double x){
21     double ans=0;
22     for(int i=0;i<n;i++)ans=max(ans,fabs(x-a[i])/b[i]);
23     return ans;
24 }
25 int main(){
26     while(scanf("%d",&n)!=EOF){
27         double maxx=-1.0*INF;
28         double minn=1.0*INF;
29         for(int i=0;i<n;i++){
30             scanf("%lf",&a[i]);
31             maxx=max(maxx,a[i]);
32             minn=min(minn,a[i]);
33         }
34         for(int i=0;i<n;i++)scanf("%lf",&b[i]);
35         double high=maxx;
36         double low=minn;
37         while(low+eps<high){
38             double mid=(high+low)/2.0;
39             double midd=(mid+high)/2.0;
40             if(fun(mid)<fun(midd))high=midd;
41             else
42                 low=mid;
43         }
44         printf("%.12f\n",fun(low));
45     }
46 }

                                                                                  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

Problem Description
In 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.
Input
The 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 )
Output
For 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.
Sample Input
1
4
0.6 5
3.9 10
5.1 7
8.4 10
Sample Output
Case #1: 832
Author
Enterpaise@UESTC_Goldfinger
Source
2012 Multi-University Training Contest 6
 我感觉这题和上面的其实很像 只是判断函数不一样而已
三分 这个 S3*W和 取最小值
#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=100000+100;
int n;
struct node{
    double x;
    double w;
}a[N];
double fun(double x){
    double ans=0.0;
    for(int i=0;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=1;k<=t;k++){
        scanf("%d",&n);
        double minn=1.0*INF;
        double maxx=-1.0*INF;
        for(int i=0;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

Problem Description
Mr. West bought a new car! So he is travelling around the city.
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?
技术分享
 
Input
Every line has four real numbers, x, y, l and w.
Proceed to the end of file.
Output
If he can go across the corner, print "yes". Print "no" otherwise.
Sample Input
10 6 13.5 4
10 6 14.5 4
Sample Output
yes
no
Source
2008 Asia Harbin Regional Contest Online
其实这个是看别人的想法 后来自己画了下图
技术分享求f(a)=l*cos(a)-(x-w/cos(a))/tan(a);

 

只要f(a)<=y  就yes 否则 no
三分 
 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 #include<map>
 5 #include<cstdlib>
 6 #include<vector>
 7 #include<set>
 8 #include<queue>
 9 #include<cstring>
10 #include<string.h>
11 #include<algorithm>
12 #define INF 0x3f3f3f3f
13 typedef long long ll;
14 typedef unsigned long long LL;
15 using namespace std;
16 const double PI=acos(-1.0);
17 const double eps=0.00000001;
18 double x,y,l,w;
19 double fun(double a){
20     double ans=l*cos(a)-(x-w/cos(a))/tan(a);
21     return ans;
22 }
23 int main(){
24     while(scanf("%lf%lf%lf%lf",&x,&y,&l,&w)!=EOF){
25         double low=0.0;
26         double high=PI/2.0;
27         if(x<w||y<w)
28         {
29             cout<<"no"<<endl;
30             continue;
31         }
32         while(low+eps<high){
33             double mid=(low+high)/2.0;
34             double midd=(mid+high)/2.0;
35             if(fun(mid)<=fun(midd)){
36                 low=mid;
37             }
38             else
39                 high=midd;
40         }
41         if(fun(low)<=y)cout<<"yes"<<endl;
42         else
43             cout<<"no"<<endl;
44     }
45 }

 

codeforces 782B The Meeting Place Cannot Be Changed+hdu 4355+hdu 2438 （三分）


联系
我们