Advertisement
prestige

Untitled

Sep 12th, 2013
193
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.47 KB | None | 0 0
  1. #include <algorithm>
  2. #include <bitset>
  3. #include <cassert>
  4. #include <cmath>
  5. #include <cstdio>
  6. #include <cstdlib>
  7. #include <cstring>
  8. #include <iostream>
  9. #include <list>
  10. #include <map>
  11. #include <queue>
  12. #include <set>
  13. #include <string>
  14. #include <sstream>
  15. #include <vector>
  16. #include <complex>
  17. #include <ctime>
  18. #include <stack>
  19.  
  20. using namespace std;
  21.  
  22. typedef long long ll;
  23. typedef unsigned long long ull;
  24. typedef vector<int> VI;
  25. typedef vector< VI > VVI;
  26. typedef pair<int, int> PII;
  27. typedef vector<PII> VPII;
  28.  
  29. #define REP(i, n) for(int i = 0; i < (n); ++i)
  30. #define RREP(i, n) for(int i = (n) - 1; i >= 0; --i)
  31. #define FOR(i, x, y) for(int i = (x); i <= (y); ++i)
  32. #define RFOR(i, x, y) for(int i = (x); i >= (y); --i)
  33. #define SZ(a) (int)(a).size()
  34. #define ALL(a) (a).begin(),(a).end()
  35. #define SORT(a) sort(ALL(a))
  36. #define CLEAR(x) memset(x, 0, sizeof x);
  37. #define COPY(FROM, TO) memcpy(TO, FROM, sizeof TO);
  38. #define UNIQUE(c) SORT(c),(c).resize(unique(ALL(c))-(c).begin())
  39. #define pb push_back
  40. #define mk make_pair
  41. #define sqr(x) ((x)*(x))
  42. #define X first
  43. #define Y second
  44. const long double pi=acos(-1.0);
  45. const double EPS = 1E-9;
  46. const int inf = 1e+9;
  47. const int NMAX = 1e+5;
  48. const int MOD = (1e+9) + 9;
  49.  
  50. double x, y, c;
  51.  
  52. struct pt {
  53. double x, y;
  54. pt () {}
  55. pt (double x_, double y_) : x(x_), y(y_) {}
  56. bool operator< (const pt & p) const {
  57. return x < p.x-EPS || abs(x-p.x) < EPS && y < p.y - EPS;
  58. }
  59. };
  60.  
  61. struct line {
  62. double a, b, c;
  63.  
  64. line() {}
  65. line (pt p, pt q) {
  66. a = p.y - q.y;
  67. b = q.x - p.x;
  68. c = - a * p.x - b * p.y;
  69. norm();
  70. }
  71.  
  72. void norm() {
  73. double z = sqrt (a*a + b*b);
  74. if (abs(z) > EPS)
  75. a /= z, b /= z, c /= z;
  76. }
  77.  
  78. double dist (pt p) const {
  79. return a * p.x + b * p.y + c;
  80. }
  81. };
  82.  
  83. #define det(a,b,c,d) (a*d-b*c)
  84.  
  85. inline bool betw (double l, double r, double x) {
  86. return min(l,r) <= x + EPS && x <= max(l,r) + EPS;
  87. }
  88.  
  89. inline bool intersect_1d (double a, double b, double c, double d) {
  90. if (a > b) swap (a, b);
  91. if (c > d) swap (c, d);
  92. return max (a, c) <= min (b, d) + EPS;
  93. }
  94.  
  95. bool intersect (pt a, pt b, pt c, pt d, pt & left, pt & right) {
  96. if (! intersect_1d (a.x, b.x, c.x, d.x) || ! intersect_1d (a.y, b.y, c.y, d.y))
  97. return false;
  98. line m (a, b);
  99. line n (c, d);
  100. double zn = det (m.a, m.b, n.a, n.b);
  101. if (abs (zn) < EPS) {
  102. if (abs (m.dist (c)) > EPS || abs (n.dist (a)) > EPS)
  103. return false;
  104. if (b < a) swap (a, b);
  105. if (d < c) swap (c, d);
  106. left = max (a, c);
  107. right = min (b, d);
  108. return true;
  109. }
  110. else {
  111. left.x = right.x = - det (m.c, m.b, n.c, n.b) / zn;
  112. left.y = right.y = - det (m.a, m.c, n.a, n.c) / zn;
  113. return betw (a.x, b.x, left.x)
  114. && betw (a.y, b.y, left.y)
  115. && betw (c.x, d.x, left.x)
  116. && betw (c.y, d.y, left.y);
  117. }
  118. }
  119.  
  120. double f (double len) {
  121. double A = sqrt (sqr(x) - sqr(len));
  122. double B = sqrt (sqr(y) - sqr(len));
  123. pt x1(0.0, 0.0), x2(0.0, 0.0);
  124. intersect (pt (len, 0), pt (0, A), pt(0, 0), pt (len, B), x1, x2);
  125. return x1.y;
  126. }
  127. double binary_search () {
  128. double first = 0, last = min (x, y) + 1;
  129. double mid;
  130. while (first < last) {
  131. if (last - first < 1e-7)
  132. return (last - first) / 2.0 + first;
  133. mid = (last - first) / 2.0 + first;
  134. double high = f (mid);
  135. if (high > c)
  136. first = mid;
  137. else
  138. last = mid;
  139. }
  140. return last;
  141. }
  142. int main () {
  143. while (scanf ("%lf %lf %lf", &x, &y, &c) != EOF) {
  144. printf ("%.3lf\n", binary_search ());
  145. }
  146. return 0;
  147. }
  148. /*
  149. 30 40 10
  150. 12.619429 8.163332 3
  151. 10 10 3
  152. 10 10 1
  153. */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement