Advertisement
double_trouble

lapta

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