Advertisement
double_trouble

lapta

Nov 14th, 2015
145
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.03 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <vector>
  4. #include <cmath>
  5. #include <string>
  6. #include <algorithm>
  7. #include <string>
  8. #include <deque>
  9. #include <iomanip>
  10.  
  11. #define F first
  12. #define S second
  13.  
  14. using namespace std;
  15.  
  16. const long double eps2 = 0.0000005;
  17. const long double eps1 = 1e-5;
  18. const long double pi = 3.1415926535897932;
  19.  
  20. struct point
  21. {
  22.     long double x;
  23.     long double y;
  24.     long double v;
  25.     point()
  26.     {
  27.         x = 0.0;
  28.         y = 0.0;
  29.         v = 0.0;
  30.     }
  31.     point(long double _x, long double _y)
  32.     {
  33.         x = _x;
  34.         y = _y;
  35.         v = -1.0;
  36.     }
  37.     point(long double _x, long double _y, long double _v)
  38.     {
  39.         x = _x;
  40.         y = _y;
  41.         v = _v;
  42.     }
  43. };
  44.  
  45. struct line
  46. {
  47.     long double a;
  48.     long double b;
  49.     long double c;
  50.     line()
  51.     {
  52.         a = 0.0;
  53.         b = 0.0;
  54.         c = 0.0;
  55.     }
  56.     line(point _a, point _b)
  57.     {
  58.         a = _b.y - _a.y;
  59.         b = _a.x-_b.x;
  60.         c = b * _a.y - a * _a.x;
  61.     }
  62. };
  63.  
  64. vector<point> a;
  65. int n;
  66. long double t;
  67. point ans;
  68.  
  69. point operator+(point a, point b)
  70. {
  71.     return point(a.x + b.x, a.y + b.y, a.v + b.v);
  72. }
  73.  
  74. point operator-(point a, point b)
  75. {
  76.     return point(a.x - b.x, a.y - b.y, a.v - b.v);
  77. }
  78.  
  79. point operator*(point a, long double k)
  80. {
  81.     return point(a.x * k, a.y * k, a.v * k);
  82. }
  83.  
  84. point operator/(point a, long double k)
  85. {
  86.     return point(a.x / k, a.y / k, a.v / k);
  87. }
  88.  
  89. long double scal(point a, point b)
  90. {
  91.     return a.x * b.x + a.y * b.y;
  92. }
  93.  
  94. long double vect(point a, point b)
  95. {
  96.     return a.x * b.y - a.y * b.x;
  97. }
  98.  
  99. long double dist(point a, point b)
  100. {
  101.     return scal(a - b, a - b);
  102. }
  103.  
  104.  
  105.  
  106. //bool out(point b, point e)
  107. //{
  108. //  if (dist(b, point()) > d && dist(e, point()) > d && dist(point(b.x, e.y), point()) > d && dist(point(e.x, b.y), point()) > d)
  109. //      return false;
  110. //  return true;
  111. //}
  112.  
  113. bool in(point g, point c)
  114. {
  115.     double r = c.v * t;
  116.     if (c.v == -1.0)
  117.         r = d;
  118.     if (fabs(r - dist(g, c)) < eps1)
  119.         return true;
  120.     return false;
  121. }
  122.  
  123. void find(point b, point e, point &ans);
  124. {
  125.     /*if (out(point b, point e))
  126.         return;*/
  127.     if (!(in(b, point() && in(e, point()) && in(point(b.x, e.y), point()) && in(point(e.x, b.y), point())))
  128.         return;
  129.     for (int i = 0; i < n; i++)
  130.     {
  131.         if (in(b, a[i]) && in(e, a[i]) && in(point(b.x, e.y), a[i]) && in(point(e.x, b.y), a[i]))
  132.             return;
  133.     }
  134.  
  135.     if (dist(e, d) < eps1)
  136.         return;
  137.     find(b, point(((e.x + b.x) / 2), (point(e.y + b.y) / 2));
  138.     find(point(((e.x + b.x) / 2), point((e.y + b.y) / 2), e);
  139.     find(point(((e.x + b.x) / 2), b.y), point(d.x, point(e.y + b.y) / 2));
  140.     find(point(b.x, ), point());
  141. }
  142.  
  143. int main()
  144. {
  145.     ios_base::sync_with_stdio(0);
  146.     //      freopen("input.txt", "r", stdin);
  147.     //      freopen("output.txt", "w", stdout);
  148.  
  149.     int n;
  150.     long double d, x, y, v;
  151.     cin >> d >> n;
  152.     for (int i = 0; i < n; i++)
  153.     {
  154.         cin >> x >> y >> v;
  155.         a.push_back(point(x, y, v));
  156.     }
  157.  
  158.     long double l = 0.0, r = 2000001.0;
  159.     while (r - l > eps2)
  160.     {
  161.         t = (l + r) / 2;
  162.         if (find(m, point(0.0, 0.0), point(d, d), ans))
  163.             l = m;
  164.         else
  165.             r = m;
  166.     }
  167.     cout << fixed;
  168.     cout << setprecision(5) << l << endl;
  169.     cout << setprecision(5) << ans.x << " " << ans.y << endl;
  170.  
  171.     return 0;
  172. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement