Madiyar

Untitled

Nov 18th, 2012
93
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.04 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <cstring>
  5. #include <algorithm>
  6. #include <cmath>
  7. #include <vector>
  8. #include <map>
  9. #include <set>
  10. #include <ctime>
  11. #include <cassert>
  12. #include <queue>
  13.  
  14. using namespace std;
  15.  
  16. #define f first
  17. #define s second
  18. #define mp make_pair
  19. #define pb push_back
  20. #define forit(it,con) for (typeof(con.begin()) it = con.begin(); it != con.end(); ++it)
  21. #define f0(a) memset(a, 0, sizeof(a))
  22. #define all(v) v.begin(), v.end()
  23. #define pii pair<int,int>
  24. #define vi vector<int>
  25. #define ll long long
  26.  
  27. #ifdef WIN32
  28.     #define I64 "%I64d"
  29. #else
  30.     #define I64 "%lld"
  31. #endif
  32. const double eps = 1e-12;
  33. struct Point {
  34.     double x, y, r;
  35.     Point () {}
  36.  
  37.     Point(double xx, double yy) {
  38.         x = xx; y = yy;
  39.     }
  40.     void read() {
  41.         scanf("%lf%lf", &x, &y);
  42.     }
  43.     void readc() {
  44.         scanf("%lf%lf%lf", &x, &y, &r);
  45.     }
  46.     Point operator - (Point a) {
  47.         return Point(x - a.x, y - a.y);
  48.     }
  49.     Point operator + (Point a) {
  50.         return Point(x + a.x, y + a.y);
  51.     }
  52.     double operator * (Point a) {
  53.         return x * a.y - y * a.x;
  54.     }
  55.     void makeLen(double len) {
  56.         double l = sqrt(x * x + y * y);
  57.         x /= l; y /= l;
  58.         x *= len; y *= len;
  59.     }
  60.     double scal(Point p) {
  61.         return x * p.x + y * p.y;
  62.     }
  63. };
  64. Point circ[1000000];
  65. int n;
  66. Point p, q;
  67. pair<double, int> A[1000000];
  68. int An;
  69.  
  70. int comp(double a,  double b) {
  71.     if (fabs(a - b) < eps) return 0;
  72.     if (a - b > eps) return 1;
  73.     return -1;
  74. }
  75.  
  76. void getLine(double &a, double &b, double &c, Point p, Point q) {
  77.     a = p.y - q.y;
  78.     b = q.x - p.x;
  79.     c = -(a * p.x + b * p.y);
  80. }
  81.  
  82. vector<Point> getInter(double a, double b, double c, Point circ) {
  83.     vector<Point> ans;
  84.     double dist = fabs(a * circ.x + b * circ.y + c);
  85.    
  86.     if (comp(dist, circ.r) >= 0) return ans;
  87.    
  88.     Point norm = Point(a, b);
  89.     Point p;
  90.  
  91.     if (comp(a, 0) != 0) p = Point(-c / a, 0); else
  92.     p = Point(0, -c / b);
  93.    
  94.     if (comp(norm.scal(circ - p), 0) > 0) norm.x *= -1, norm.y *= -1;
  95.     norm.makeLen(dist);
  96.    
  97.     p = circ + norm;
  98.     Point vec = Point(-b, a);
  99.     vec.makeLen(sqrt(circ.r * circ.r - dist * dist));
  100.     ans.pb(vec + p);
  101.     ans.pb(p - vec);
  102.     return  ans;
  103. }
  104. int main() {
  105.     freopen("horseraces.in","r",stdin);
  106.     freopen("horseraces.out","w",stdout);
  107.     p.read(); q.read();
  108.     scanf("%d", &n);
  109.     for (int i = 0; i < n; ++i)
  110.         circ[i].readc();
  111.     double a, b, c;
  112.     getLine(a, b, c, p, q);
  113.     double d = sqrt(a * a + b * b);
  114.     a /= d; b /= d; c /= d;
  115.    
  116.     Point dv = q - p;
  117.     dv.makeLen(1);
  118.  
  119.     for (int i = 0; i < n; ++i) {
  120.         vector<Point> tmp = getInter(a, b, c, circ[i]);
  121.         if (tmp.size() != 2) continue;
  122.         double t1, t2;
  123.         if (comp(dv.x, 0) != 0) {
  124.             t1 = (tmp[0].x - p.x) / dv.x;
  125.             t2 = (tmp[1].x - p.x) / dv.x;
  126.         } else {
  127.             t1 = (tmp[0].y - p.y) / dv.y;
  128.             t2 = (tmp[1].y - p.y) / dv.y;
  129.        
  130.         }
  131.         if (comp(t1, t2) > 0) swap(t1, t2);
  132.  
  133.         A[An++] = mp(t1, 0);
  134.         A[An++] = mp(t2, 1);
  135.     }
  136.     sort(A, A + An);
  137.     int op = 0;
  138.     double ans = 0;
  139.     for (int i = 0; i < An; ++i) {
  140.         if (op > 0) ans += A[i].f - A[i - 1].f;
  141.         if (A[i].s == 0) ++op; else
  142.         --op;
  143.     }
  144.     printf("%.6lf", ans);
  145.     return 0;
  146. }
Advertisement
Add Comment
Please, Sign In to add comment