oj.uz

Submission #533042

# Submission time Handle Problem Language Result Execution time Memory
533042 2022-03-04T14:38:45 Z Stormersyle Mobile (BOI12_mobile) C++17
0 / 100
 1000 ms 54300 KB 
#include <iostream>
#include <bits/stdc++.h> 
#include <array>
#include <fstream>
#include <string>
#include <algorithm>
#include <cmath>
#include <sstream>  
#include <iomanip>
using namespace std;
using ll=long long;

double N, L;
vector<pair<double, double>> c; //{x, y}

bool check(double R){ //checks to see if max distance >=R is possible; find last true
  vector<pair<double, double>> I;
  for (pair<double, double> coord: c){
    double x=coord.first, y=coord.second;
    I.push_back({x-sqrt(R*R-y*y), x+sqrt(R*R-y*y)});
  }
  sort(I.begin(), I.end());
  // for (auto p: I) cout<<"("<<p.first<<" "<<p.second<<")  ";
  // cout<<"\n";
  int s=0;
  double M=-1000000000; //M=max endpoint so far
  while (I[s].first<0) M=max(M, I[s].second), s++;
  for (int i=s; i<N; i++){ //since I.size()==N
    if (I[i].first>M) return true;
    M=max(M, I[i].second);
  }
  if (L>M) return true;
  return false;
}

int main() {
  cin>>N>>L;
  for (int i=0; i<N; i++){
    double x, y;
    cin>>x>>y;
    c.push_back({x, y});
  }

  ll lo=0, hi=1000000000000000;
	lo--;
	while (lo < hi) {
		ll mid = lo + (hi - lo + 1) / 2;
    double R=mid/1000000.0;
		if (check(R)) {
			lo = mid;
		} else {
			hi = mid - 1;
		}
	}
	cout<<setprecision(8)<<lo/1000000.0;
  // cout<<check(5);
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 432 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 632 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 620 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 636 KB Output is correct
2 Incorrect 14 ms 656 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 331 ms 5656 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 340 ms 5552 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 256 ms 5920 KB Output is correct
2 Incorrect 360 ms 6104 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #10
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 401 ms 7060 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 315 ms 7040 KB Output is correct
2 Incorrect 475 ms 7032 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #12
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1090 ms 28656 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #13
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1083 ms 30608 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #14
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1042 ms 40740 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #15
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1080 ms 41920 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #16
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1089 ms 44748 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #17
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1056 ms 45012 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #18
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1081 ms 48220 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #19
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1008 ms 48036 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #20
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1064 ms 54300 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #21
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1054 ms 22188 KB Time limit exceeded
2 Halted 0 ms 0 KB -