oj.uz

Submission #799319

# Submission time Handle Problem Language Result Execution time Memory
799319 2023-07-31T12:36:42 Z tch1cherin Mobile (BOI12_mobile) C++17
8 / 100
 1000 ms 97252 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 = 1e18;
  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;
    }
  }
  cout << r << "\n";
}

Subtask #1
0 / 4.0

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

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 348 KB Output is correct
2 Correct 2 ms 320 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 33 ms 660 KB Output is correct
2 Incorrect 33 ms 856 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 67 ms 948 KB Output is correct
2 Correct 100 ms 1104 KB Output is correct
3 Correct 91 ms 952 KB Output is correct
4 Correct 59 ms 976 KB Output is correct

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 956 KB Output is correct
2 Correct 98 ms 984 KB Output is correct
3 Correct 103 ms 956 KB Output is correct
4 Correct 53 ms 1108 KB Output is correct

Subtask #6
0 / 5.0

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

Subtask #7
0 / 5.0

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

Subtask #8
0 / 5.0

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

Subtask #9
0 / 5.0

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

Subtask #10
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1053 ms 12388 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 1069 ms 12248 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 1066 ms 52348 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 1054 ms 56360 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 1074 ms 73572 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 1051 ms 78272 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 1065 ms 77484 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 1028 ms 83000 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 1047 ms 81448 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 1064 ms 87768 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 89564 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 1069 ms 97252 KB Time limit exceeded
2 Halted 0 ms 0 KB -