Submission #199185

#TimeUsernameProblemLanguageResultExecution timeMemory
199185imaxblueMobile (BOI12_mobile)C++17
0 / 100
358 ms40636 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define mp make_pair #define pb push_back #define x first #define y second #define pii pair<int, int> #define p3i pair<pii, int> #define pll pair<ll, ll> #define p3l pair<pll, ll> #define vi vector<int> #define vpii vector<pii> #define vp3i vector<p3i> #define vpll vector<pll> #define vp3l vector<p3l> #define lseg L, (L+R)/2, N*2+1 #define rseg (L+R)/2+1, R, N*2+2 #define ub upper_bound #define lb lower_bound #define pq priority_queue #define MN 1000000007 #define fox(k, x) for (int k=0; k<x; ++k) #define fox1(k, x) for (int k=1; k<=x; ++k) #define foxr(k, x) for (int k=x-1; k>=0; --k) #define fox1r(k, x) for (int k=x; k>0; --k) #define ms multiset #define flood(x) memset(x, 0x3f3f3f3f, sizeof x) #define drain(x) memset(x, 0, sizeof x) #define rng() ((rand() << 14)+rand()) #define scan(X) do{while((X=getchar())<'0'); for(X-='0'; '0'<=(_=getchar()); X=(X<<3)+(X<<1)+_-'0');}while(0) char _; #define pi 3.14159265358979323846 #define startrng mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); long double ans; int n, d, x, y; vector<pll> v; vector<pll> hull; //f(x) = x^2 + mx + b //xa1+b1=xa2+b2 //x=(b2-b1)/(a1-a2); long double eval(pll A, long double X){ //cout << A.x << ' ' << A.y << ' ' << X << endl; return sqrt(X*X+X*A.x+A.y); } void check(pll A, pll B){ long double x=(B.y-A.y)/((long double)(A.x-B.x)); if (x<0 || x>d) return; ans = max(eval(A, x), ans); } bool cross(pll A, pll O, pll B){ return (A.x-O.x)/double(B.x-O.x)<=double(A.y-O.y)/(B.y-O.y)-(1e-9); } int32_t main(){ scanf("%i%i", &n, &d); fox(l, n){ scanf("%i%i", &x, &y); v.pb(mp(-2*x, 1LL*y*y+1LL*x*x)); } sort(v.begin(), v.end()); for (auto i:v){ while(hull.size()>1 && cross(hull[hull.size()-2], hull.back(), i)){ hull.pop_back(); } hull.pb(i); } fox(l, hull.size()-1){ check(hull[l], hull[l+1]); } //cout << hull.size() << endl; //cout << ans << endl; long double lft=(1LL<<62), rit=(1LL<<62); fox(l, hull.size()){ lft=min(lft, eval(hull[l], 0)); rit=min(rit, eval(hull[l], d)); } //cout << lft << ' ' << rit << endl; ans = max(ans, max(lft, rit)); //cout << sqrt(ans) << endl; printf("%.8Lf", ans); return 0; } /* 3 10 0 0 5 1000000000 11 1 */

Compilation message (stderr)

mobile.cpp: In function 'int32_t main()':
mobile.cpp:23:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define fox(k, x) for (int k=0; k<x; ++k)
mobile.cpp:68:7:
   fox(l, hull.size()-1){
       ~~~~~~~~~~~~~~~~            
mobile.cpp:68:3: note: in expansion of macro 'fox'
   fox(l, hull.size()-1){
   ^~~
mobile.cpp:23:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define fox(k, x) for (int k=0; k<x; ++k)
mobile.cpp:74:7:
   fox(l, hull.size()){
       ~~~~~~~~~~~~~~              
mobile.cpp:74:3: note: in expansion of macro 'fox'
   fox(l, hull.size()){
   ^~~
mobile.cpp:56:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%i%i", &n, &d);
   ~~~~~^~~~~~~~~~~~~~~~
mobile.cpp:58:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i%i", &x, &y);
     ~~~~~^~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...