Submission #699432

#	Time	Username	Problem	Language	Result	Execution time	Memory
699432		vjudge1	Balloons (CEOI11_bal)	C++17	40 / 100	2090 ms	4948 KiB

bal

#include <bits/stdc++.h>

using namespace std;
using lint = int64_t;
using ld = long double;

constexpr int _mod = int(1e9) + 7;
constexpr int _inf = 0x3f3f3f3f;
constexpr int _ninf = 0xcfcfcfcf;
constexpr lint _linf = 0x3f3f3f3f3f3f3f3f;

#define endl '\n'

template<class T>
struct Point {
  typedef Point P;
  T x, y;
  explicit Point(T x=0, T y=0) : x(x), y(y) {}
  bool operator==(P p) const {return tie(x, y) == tie(p.x, p.y); }
  P operator+(P p) const {return P(x+p.x, y+p.y); }
  P operator-(P p) const {return P(x-p.x, y-p.y); }
  P operator*(T d) const {return P(x*d, y*d); }
  P operator/(T d) const {return P(x/d, y/d); }
  T dist2() const { return x*x + y*y;}
  ld dist() const { return sqrt((ld)dist2());}
  P perp() const { return P(-y, x); }
};

using P = Point<ld>;

bool circleInter(P a, P b, ld r1, ld r2) {
  if(a == b) {assert(r1 != r2); return false;}
  P vec = b - a;
  ld d2 = vec.dist2(), sum = r1+r2, dif = r1-r2, p = (d2 + r1*r1 - r2*r2)/(d2*2), h2 = r1*r1 - p*p*d2;
  if(sum * sum < d2 || dif*dif > d2) return false;
  P mid = a + vec*p, per = vec.perp() * sqrt(fmax(0, h2) / d2);
  return true;
}

int cmp_double(ld a, ld b = 0, ld eps = 1e-9) {
  return a + eps > b ? b + eps > a ? 0 : 1 : -1;
}

int n;
vector<pair<int,int>> v;
vector<ld> ans;

bool hasInter(int idx) {
  P current(v[idx].first, ans[idx]);
  ld rc = ans[idx];
  for(int i = idx - 1; i >= 0; i--) {
    ld rp = ans[i];
    P p(v[i].first, rp);
    if(circleInter(p, current, rp, rc)) return true;
  }
  return false;
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false); 
  cin >> n;

  v.resize(n);
  ans.resize(n);

  for(auto &i : v) cin >> i.first >> i.second;

  ans[0] = v[0].second;

  for(int i = 1; i < n; i++) {
    P pl(v[i-1].first, ans[i-1]);

    ld l = 0, r = v[i].second, mid;
    while(cmp_double(l, r) != 0) {
      mid = (l + r)/2;
      ans[i] = mid;
      if(hasInter(i)) r = mid;
      else l = mid;
    }
  }
  
  for(auto i : ans) cout << fixed << setprecision(3) << i << endl;

  
  return 0;
}

Compilation message (stderr)

bal.cpp: In function 'bool circleInter(P, P, ld, ld)':
bal.cpp:36:5: warning: variable 'mid' set but not used [-Wunused-but-set-variable]
   36 |   P mid = a + vec*p, per = vec.perp() * sqrt(fmax(0, h2) / d2);
      |     ^~~
bal.cpp:36:22: warning: variable 'per' set but not used [-Wunused-but-set-variable]
   36 |   P mid = a + vec*p, per = vec.perp() * sqrt(fmax(0, h2) / d2);
      |                      ^~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10