Submission #133186

#TimeUsernameProblemLanguageResultExecution timeMemory
133186sealnot123Mobile (BOI12_mobile)C++14
100 / 100
362 ms40608 KiB
#include<bits/stdc++.h> #define x first #define y second #define pb push_back #define eb emplace_back #define all(a) (a).begin(),(a).end() #define SZ(a) (int)(a).size() using namespace std; typedef long long LL; typedef pair<LL,LL> PLL; typedef pair<int,int> PII; typedef double D; typedef long double LD; const int N = 1000007; vector<PLL> tower; bool cmp(PLL a, PLL b){ if(a.x != b.x) return a.x > b.x; return a.y < b.y; } PLL intersect(PLL a, PLL b){ LL A, B; A = a.y - b.y; B = b.x - a.x; if(B < 0) A = -A, B = -B; return {A, B}; } vector<PLL> line; void add(PLL nw){ while(SZ(line)>1){ int a = SZ(line); if(line[a-1].x == nw.x) return; PLL tmp1 = intersect(line[a-2], line[a-1]); PLL tmp2 = intersect(line[a-1], nw); if((__int128)tmp2.x*(__int128)tmp1.y <= (__int128)tmp1.x*(__int128)tmp2.y) line.pop_back(); else break; } line.pb(nw); } LD calc(LD a, int b){ return a*line[b].x + line[b].y; } LL L; int n; int main(){ int i,j; LL a,b, dist0 = 2e18+2, distL = 2e18+2; LD ans; scanf("%d %lld",&n,&L); for(i=1;i<=n;i++){ scanf("%lld%lld",&a,&b); dist0 = min(dist0, a*a + b*b); distL = min(distL, (L-a)*(L-a) + b*b); if(tower.empty() || tower.back().x != -a*2) tower.pb({-a*2, a*a + b*b}); else tower.back().y = min(tower.back().y, a*a + b*b); } ans = (LD)max(dist0, distL); n = SZ(tower); for(i=0;i<n;i++) add(tower[i]); for(i = 0; i < SZ(line)-1; i++){ PLL tmp = intersect(line[i], line[i+1]); LD tmp2 = (LD)tmp.x/tmp.y; if(tmp2 < 0 || tmp2 > L) continue; ans = max(ans, calc(tmp2, i) + tmp2*tmp2); } printf("%Lf",sqrt(ans)); return 0; } /* 2 10 0 0 11 1 3 10 1 0 5 0 10 0 2 10 -5 3 12 2 */

Compilation message (stderr)

mobile.cpp: In function 'int main()':
mobile.cpp:52:8: warning: unused variable 'j' [-Wunused-variable]
  int i,j;
        ^
mobile.cpp:55:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %lld",&n,&L);
  ~~~~~^~~~~~~~~~~~~~~~~
mobile.cpp:57:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld",&a,&b);
   ~~~~~^~~~~~~~~~~~~~~~~~
#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...