Submission #799327

#	Time	Username	Problem	Language	Result	Execution time	Memory
799327		tch1cherin	Mobile (BOI12_mobile)	C++17	13 / 100	1074 ms	81292 KiB

mobile

#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
• Subtask 2: 0 / 4
• Subtask 3: 0 / 4
• Subtask 4: 4 / 4
• Subtask 5: 4 / 4
• Subtask 6: 0 / 5
• Subtask 7: 0 / 5
• Subtask 8: 5 / 5
• Subtask 9: 0 / 5
• Subtask 10: 0 / 5
• Subtask 11: 0 / 5
• Subtask 12: 0 / 5
• Subtask 13: 0 / 5
• Subtask 14: 0 / 5
• Subtask 15: 0 / 5
• Subtask 16: 0 / 5
• Subtask 17: 0 / 5
• Subtask 18: 0 / 5
• Subtask 19: 0 / 5
• Subtask 20: 0 / 5
• Subtask 21: 0 / 5