Submission #772277

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
772277	2023-07-03 21:12:44	hanlulu	Balloons (CEOI11_bal)	C++14	100 / 100	148 ms	8788 KiB

bal

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/*https://oj.uz/problem/view/CEOI11_bal
first, if pre ballon radius is R, positon is x, new radius is r, position is y
we got (R+r)^2= (R-r)^2 +(y-x)^2  => r= (y-x)^2/ 4R
sort by position, for each ballon, if it's radius bigger than pre ones, the pre ones will never impact future one
so, we use stack save all radius, for new one , compare all ones in stack, compare with them find the real R.
for each new R, if it's bigger than pre one, pop pre one. 
 */
#include <bits/stdc++.h>
using namespace std;
double getr(double lastx,double lastr,double x){
  return (x-lastx) * (x-lastx) / 4 / lastr;
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0); 
  cout.tie(0);
  //freopen("hayfeast.in","r",stdin);
  //freopen("hayfeast.out","w",stdout);
  int n;
  cin >> n ;
  vector <double> ans(n);//save answer
  stack<pair<double,double>> st;//first, x second, r
  double x,r;//r is limitation for radius
  for (int i = 0; i < n; i++) {
    cin >> x >> r;
    while (!st.empty()) {
      double lastr = st.top().second;
      double lastx = st.top().first;
      double maxr = getr(lastx,lastr,x);
      r = min(r,maxr);
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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