Submission #112546

#	Time	Username	Problem	Language	Result	Execution time	Memory
112546		zoooma13	Mobile (BOI12_mobile)	C++14	0 / 100	1071 ms	512 KiB

mobile

#include <bits/stdc++.h>
using namespace std;

#define MAX_N 5003

int n ,l;
int x[MAX_N] ,y[MAX_N];

double dist(int x ,int y ,double p){
    return sqrt(1.0*y*y + 1.0*(p-x)*(p-x));
}
double get_min(double p){
    double ret = DBL_MAX;
    for(int i=0; i<n; i++)
        ret = min(ret ,dist(x[i] ,y[i] ,p));
    return ret;
}
double fnd_rng(double st ,double en ,int i ,bool le){
    double mid;
    for(int ee=200; ee; ee--){
        mid = (st+en)/2;
        if(get_min(mid)-dist(x[i] ,y[i] ,mid) >= 0)
            (le ? en = mid : st = mid);
        else
            (le ? st = mid : en = mid);
    }
    return le ? en : st;
}

double naive(){
    double ans = DBL_MIN;
    for(double i=0; i<=l; i+=0.0001)
        ans = max(ans ,get_min(i));
    return ans;
}

int main()
{
    scanf("%d%d",&n,&l); assert(n < MAX_N);
//n = 10 ,l = 20;
//printf("%d %d\n",n,l);
    for(int i=0; i<n; i++)
        scanf("%d%d",&x[i],&y[i]);
/*{x[i] = (rand()%20)*(rand()%5 ? +1 : -1) ,y[i] = (rand()%20)*(rand()%5 ? +1 : -1);
printf("%d %d\n",x[i],y[i]);}*/

    double ans = DBL_MIN;
    for(int i=0; i<n; i++)
    {
        double st = fnd_rng(0 ,x[i] ,i ,1);
        double en = fnd_rng(x[i] ,l ,i ,0);
        if(en-st>1e-7)
            ans = max(ans ,max(dist(x[i] ,y[i] ,st) ,dist(x[i] ,y[i] ,en)));
    }

    cout << fixed << setprecision(6) << ans << endl;
}

Compilation message (stderr)

mobile.cpp: In function 'int main()':
mobile.cpp:39:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&n,&l); assert(n < MAX_N);
     ~~~~~^~~~~~~~~~~~~~
mobile.cpp:43:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&x[i],&y[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 4
• Subtask 2: 0 / 4
• Subtask 3: 0 / 4
• Subtask 4: 0 / 4
• Subtask 5: 0 / 4
• Subtask 6: 0 / 5
• Subtask 7: 0 / 5
• Subtask 8: 0 / 5
• Subtask 9: 0 / 5
• Subtask 10: 0 / 5
• Subtask 11: 0 / 5
• Subtask 12: 0 / 5
• Subtask 13: 0 / 5
• Subtask 14: 0 / 5
• Subtask 15: 0 / 5
• Subtask 16: 0 / 5
• Subtask 17: 0 / 5
• Subtask 18: 0 / 5
• Subtask 19: 0 / 5
• Subtask 20: 0 / 5
• Subtask 21: 0 / 5