oj.uz

Submission #799327

# Submission time Handle Problem Language Result Execution time Memory
799327 2023-07-31T12:42:00 Z tch1cherin Mobile (BOI12_mobile) C++17
13 / 100
 1000 ms 81292 KB 
#include <bits/stdc++.h>
using namespace std;

using D = long double;

struct Point {
  D x, y;
  
  Point operator+(Point b) { return {x + b.x, y + b.y}; }

  Point operator-(Point b) { return {x - b.x, y - b.y}; }

  Point operator*(D k) { return {x * k, y * k}; }
};

D dot(Point a, Point b) { return a.x * b.x + a.y * b.y; }

D cross(Point a, Point b) { return a.x * b.y - a.y * b.x; }

D norm(Point a) { return dot(a, a); }

D length(Point a) { return sqrtl(norm(a)); }

Point normalize(Point a, D k) { return a * (k / length(a)); }

D pointToLine(Point C, Point A, Point B) {
  return abs(cross(C - A, C - B) / length(B - A));
}

Point getHeight(Point C, Point A, Point B) {
  Point v = B - A;
  return A + normalize(v, dot(v, C - A) / length(v));
}

D dequal(D a, D b) { return abs(a - b) < 1e-12l; }

D dless(D a, D b) { return a < b && !dequal(a, b); }

D sqr(D a) { return a * a; }

bool isZero(Point a) { return dequal(a.x, 0) && dequal(a.y, 0); }

vector<Point> getIntersection(Point O, D r, Point A, Point B) {
  D h = pointToLine(O, A, B);
  if (dless(r, h)) {
    return {};
  }
  Point H = getHeight(O, A, B);
  Point v = B - A;
  v = normalize(v, sqrtl(sqr(r) - sqr(h)));
  if (isZero(v)) {
    return {H};
  } else {
    return {H - v, H + v};
  }
}

int main() {
  cout << fixed << setprecision(9);
  cin.tie(nullptr)->sync_with_stdio(false);
  int N, L;
  cin >> N >> L;
  vector<Point> points(N);
  for (auto &[x, y] : points) {
    cin >> x >> y;
  }
  D l = 0, r = 1e9;
  for (int i = 0; i < 100; i++) {
    D R = (l + r) / 2;
    vector<pair<D, D>> seg;
    for (auto p : points) {
      vector<Point> I = getIntersection(p, R, {0, 0}, {(D)L, 0});
      if (I.size() == 1) {
        seg.push_back({I[0].x, I[0].x});
      } else if (I.size() == 2) {
        if (I[0].x > I[1].x) {
          swap(I[0], I[1]);
        }
        seg.push_back({I[0].x, I[1].x});
      }
    }
    sort(seg.begin(), seg.end());
    long double max_r = 0;
    bool good = true;
    for (auto [ll, rr] : seg) {
      if (dless(L, ll)) {
        break;
      }
      if (dless(max_r, ll)) {
        good = false;
      } else {
        max_r = max(max_r, rr);
      }
    }
    if (good) {
      r = R;
    } else {
      l = R;
    }
  }
  assert(!dequal(r, 1e9));
  cout << r << "\n";
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 320 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

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

Subtask #3
0 / 4.0

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

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 956 KB Output is correct
2 Correct 85 ms 972 KB Output is correct
3 Correct 90 ms 1000 KB Output is correct
4 Correct 37 ms 996 KB Output is correct

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 956 KB Output is correct
2 Correct 84 ms 1128 KB Output is correct
3 Correct 93 ms 952 KB Output is correct
4 Correct 36 ms 996 KB Output is correct

Subtask #6
0 / 5.0

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

Subtask #7
0 / 5.0

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

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 668 ms 9488 KB Output is correct
2 Correct 563 ms 9244 KB Output is correct
3 Correct 614 ms 9784 KB Output is correct
4 Correct 561 ms 9768 KB Output is correct
5 Correct 563 ms 10116 KB Output is correct

Subtask #9
0 / 5.0

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

Subtask #10
0 / 5.0

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

Subtask #11
0 / 5.0

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

Subtask #12
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1059 ms 48272 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 1066 ms 48348 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 1055 ms 68620 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 1063 ms 68592 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 1060 ms 71768 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 1072 ms 71928 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 1071 ms 74784 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 1070 ms 74888 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 1056 ms 81292 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 1074 ms 81128 KB Time limit exceeded
2 Halted 0 ms 0 KB -