Advertisement
artemgf

Точность попадания снаряда

Feb 4th, 2018
122
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.68 KB | None | 0 0
  1. #define _USE_MATH_DEFINES
  2. #include <iostream>
  3. #include <string>
  4. #include <map>
  5. #include <set>
  6. #include <algorithm>
  7. #include <vector>
  8. #include <stdio.h>
  9. #include <cmath>
  10. #include <math.h>
  11. #include <queue>
  12. #include <stack>
  13. #include <climits>
  14. #include <deque>
  15. #include <ctime>
  16.  
  17. using namespace std;
  18.  
  19. typedef long long ll;
  20. typedef unsigned long long ull;
  21. typedef unsigned int ui;
  22.  
  23. #define mh() make_heap()
  24. #define poph() pop_heap()
  25. #define pushh() push_heap()
  26. #define sor(n) n.begin(), n.end()
  27. #define rsor(n) n.rbegin(), n.rend()
  28. #define mp make_pair
  29. #define files freopen("input.txt", "rt", stdin); freopen("output.txt", "wt", stdout)
  30. #define p(T) pair<T,T>
  31. #define znac(l) abs(l)/l
  32.  
  33. #define A(y1,y2) y1-y2
  34. #define B(x1,x2) x2-x1
  35. #define C(x1,y1,x2,y2) -y2*(x2-x1)-x2*(y1-y2)
  36.  
  37. #define rs(x1,y1,x2,y2) sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1))
  38.  
  39. struct pt {
  40.     double x, y;
  41. };
  42.  
  43. struct line {
  44.     double a, b, c;
  45. };
  46.  
  47. const double EPS = 1e-9;
  48.  
  49. double det(double a, double b, double c, double d) {
  50.     return a * d - b * c;
  51. }
  52.  
  53. bool intersect(line m, line n, pt & res) {
  54.     double zn = det(m.a, m.b, n.a, n.b);
  55.     if (abs(zn) < EPS)
  56.         return false;
  57.     res.x = -det(m.c, m.b, n.c, n.b) / zn;
  58.     res.y = -det(m.a, m.c, n.a, n.c) / zn;
  59.     return true;
  60. }
  61.  
  62. bool parallel(line m, line n) {
  63.     return abs(det(m.a, m.b, n.a, n.b)) < EPS;
  64. }
  65.  
  66. bool equivalent(line m, line n) {
  67.     return abs(det(m.a, m.b, n.a, n.b)) < EPS
  68.         && abs(det(m.a, m.c, n.a, n.c)) < EPS
  69.         && abs(det(m.b, m.c, n.b, n.c)) < EPS;
  70. }
  71.  
  72. double MIN(p(double)fr, p(double)sc, p(double)t)
  73. {
  74.     line frst = { A(fr.second,sc.second),B(fr.first,sc.first),C(fr.first,fr.second,sc.first,sc.second) };
  75.     line sec = {-frst.b,frst.a,frst.b*t.first-frst.a*t.second };
  76.     if (!parallel(frst, sec) && !equivalent(frst, sec))
  77.     {
  78.         pt res;
  79.         intersect(frst, sec, res);
  80.         double l = rs(fr.first, fr.second, sc.first, sc.second);
  81.         double ll = rs(fr.first, fr.second, res.x, res.y);
  82.         double lr = rs(res.x, res.y, sc.first, sc.second);
  83.         if (abs(l-(ll + lr)) > EPS)
  84.         {
  85.             return min(rs(fr.first, fr.second, t.first, t.second), rs(t.first, t.second, sc.first, sc.second));
  86.         }
  87.         else
  88.         {
  89.             double H = abs((frst.a*t.first +frst.b*t.second + frst.c) / sqrt(frst.a*frst.a + frst.b*frst.b));
  90.             return min(H, min(rs(fr.first, fr.second, t.first, t.second), rs(t.first, t.second, sc.first, sc.second)));
  91.         }
  92.     }
  93.     else
  94.     {
  95.         return min(rs(fr.first, fr.second, t.first, t.second), rs(t.first, t.second, sc.first, sc.second));
  96.     }
  97. }
  98.  
  99. int main()
  100. {
  101. #ifndef ONLINE_JUDGE
  102.     files;
  103. #endif
  104.    
  105.     p(double) t;
  106.     ll n;
  107.    
  108.     cin >> t.first >> t.second>>n;
  109.     vector<p(double)>cord(n + 1);
  110.     for (int i = 1; i <= n; i++)
  111.     {
  112.         cin >> cord[i].first >> cord[i].second;
  113.     }
  114.     ll last = 0;
  115.     bool good = 1;
  116.     for (int i = 1; i <= n; i++)
  117.     {
  118.         double ras;
  119.         line frst;
  120.         if (i == 1)
  121.         {
  122.             frst = { A(cord[i].second,cord[n].second),B(cord[i].first,cord[n].first),C(cord[i].first,cord[i].second,cord[n].first,cord[n].second) };
  123.         }
  124.         else
  125.             frst = { A(cord[i].second,cord[i-1].second),B(cord[i].first,cord[i-1].first),C(cord[i].first,cord[i].second,cord[i-1].first,cord[i-1].second) };
  126.         double H = (frst.a*t.first + frst.b*t.second + frst.c) / sqrt(frst.a*frst.a + frst.b*frst.b);
  127.         if (last == 0)
  128.         {
  129.             last = znac(H);
  130.         }
  131.         else
  132.         {
  133.             if (abs(H) < EPS)
  134.             {
  135.             }
  136.             else
  137.                 if (last != znac(H))
  138.                 {
  139.                     good = 0;
  140.                     break;
  141.                 }
  142.         }
  143.     }
  144.     if (good)
  145.     {
  146.         printf("%.3lf", 0.0);
  147.         return 0;
  148.     }
  149.     double answ = INT_MAX;
  150.     for (int i = 1; i <= n; i++)
  151.     {
  152.         double ras;
  153.         if (i == 1)
  154.         {
  155.             ras = MIN(cord[i], cord[n], t);
  156.         }
  157.         else
  158.         {
  159.             ras = MIN(cord[i], cord[i-1], t);
  160.         }
  161.         answ = min(answ, ras);
  162.     }
  163.     printf("%.3lf", 2*answ);
  164.     return 0;
  165. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement