Advertisement
Mlxa

ALGO circleGeometry

Mar 25th, 2018
112
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 5.45 KB | None | 0 0
  1. #include <cmath>
  2. #include <cassert>
  3. #include <cstdio>
  4. #include <iostream>
  5. #include <iomanip>
  6. #include <vector>
  7. #ifdef AC
  8.     #define __GLIBCXX_DEBUG
  9.     #define __GLIBCXX_ASSERT
  10. #endif
  11. using namespace std;
  12.  
  13. #define all(x) begin(x), end(x)
  14. template<class A> void addlog(A a) { cerr << a << endl; }
  15. template<class A, class... B> void addlog(A a, B... b)
  16. { cerr << a << ' '; addlog(b...); }
  17.  
  18.  
  19. namespace floatGeometry {
  20.     // Types
  21.     #define pcout cout << fixed << setprecision(7)
  22.     typedef long long ll;
  23.     typedef long double ld;
  24.     const ld eps = 1e-12;
  25.     const ld inf = 1e+12;
  26.     bool eq (ld a, ld b) { return abs(a - b) < eps; }
  27.     ld abs (ld x) { return (x > 0? x : -x); }
  28.     struct Point { ld x, y; };
  29.     typedef Point Vector;
  30.     const ld PI = 3.14159265358979L;
  31.     ld toGradus (ld rad) { return (180 * rad) / PI; }
  32.     ld toRad (ld gradus) { return (PI * gradus) / 180; }
  33.    
  34.     // Constants
  35.     const Point     NO_POINT    {19, -inf},
  36.                     POINTS      {19, +inf};
  37.     // Point
  38.     ld abs (Point p) { return hypot(p.x, p.y); }
  39.     ld ang (Point p) { return atan2(p.y, p.x); }
  40.     bool operator== (Point a, Point b)
  41.     { return eq(a.x, b.x) && eq(a.y, b.y); }
  42.     bool operator!= (Point a, Point b)
  43.     { return !(a == b); }
  44.     // Vector
  45.     Vector operator- (Vector v)
  46.     { return Vector{ -v.x, -v.y }; }
  47.     Vector operator+ (Vector a, Vector b)
  48.     { return Vector{ a.x+b.x, a.y+b.y }; }
  49.     Vector operator- (Vector a, Vector b)
  50.     { return Vector{ a.x-b.x, a.y-b.y }; }
  51.     Vector operator* (Vector v, ld alpha)
  52.     { return Vector{ alpha * v.x, alpha * v.y }; }
  53.     ld operator* (Vector a, Vector b)
  54.     { return a.x*b.y - b.x*a.y; }
  55.     ld operator% (Vector a, Vector b)
  56.     { return a.x*b.x + a.y*b.y; }
  57.     Vector turn90 (Vector v)
  58.     { return Vector{v.y, -v.x}; }
  59.     ld ang (Vector a, Vector b) {
  60.         return atan2(a * b, a % b);
  61.     }
  62.     // I/O.
  63.     istream& operator>> (istream& s, Point &p)
  64.     { return s >> p.x >> p.y; }
  65.     ostream& operator<< (ostream &s, Point p)
  66.     { return s << p.x << ' ' << p.y; }
  67.    
  68.    
  69.     struct Segment { Point p, q; };
  70.     ld abs (Segment s) { return abs(s.p - s.q); }
  71.    
  72.     istream& operator>> (istream &s, Segment &x)
  73.     { return s >> x.p >> x.q; }
  74.     ostream& operator<< (ostream &s, Segment x)
  75.     { return s << x.p << "  " << x.q; }
  76.    
  77.     struct Line { ld a, b, c; Line () {}
  78.         void normalize () {
  79.             ld z = hypot(a, b);
  80.             if (eq(a, 0)) { if (b < 0) z = -z; }
  81.             else if (a < 0) z = -z;
  82.             a /= z; b /= z; c /= z;
  83.                                                                         assert(eq(hypot(a, b), 1));
  84.         } Line (Point p, Point q) {
  85.             a = p.y - q.y; b = q.x - p.x;
  86.             c = - (a * p.x + b * p.y );
  87.             normalize();
  88.         } Line (Segment s) : Line(s.p, s.q) {}
  89.     };
  90.    
  91.     // Line
  92.     ld vMul (ld ax, ld ay, ld bx, ld by) { return ax*by - bx*ay; }
  93.     Point intersect (Line I, Line II) {
  94.         ld D0 = vMul(I.a, I.b, II.a, II.b);
  95.         ld Dx = vMul(I.b, I.c, II.b, II.c);
  96.         ld Dy = vMul(I.c, I.a, II.c, II.a);
  97.         if (eq(D0, 0)) {
  98.             assert(eq(Dx, Dy));
  99.             if (eq(Dx, 0))  return POINTS;
  100.             else            return NO_POINT;
  101.         } return Point{Dx / D0, Dy / D0};
  102.     }
  103.     // I/O
  104.     istream& operator>> (istream& s, Line &l)
  105.     { return s >> l.a >> l.b >> l.c; }
  106.     ostream& operator<< (ostream& s, Line l)
  107.     { return s << l.a << ' ' << l.b << ' ' << l.c; }
  108.    
  109.     struct Ray {
  110.         Point p; Vector v; Line l;
  111.         Ray (Point P, Vector V) : p(P), v(V), l(p, p + v) {}
  112.     };
  113.    
  114.     ld signDist (Line l, Point p) {
  115.         l.normalize();
  116.         return l.a * p.x + l.b * p.y + l.c;
  117.     } ld dist (Line l, Point p) { return abs(signDist(l, p)); }
  118.    
  119.     ld dist (Ray r, Point p) {
  120.         if ( (p - r.p) % r.v > -eps )
  121.             return dist(r.l, p);
  122.         else return abs(p - r.p);
  123.     }
  124.    
  125.     ld dist (Segment s, Point p) {
  126.         Ray r1 (s.p, s.q - s.p),
  127.             r2 (s.q, s.p - s.q);
  128.         return max(dist(r1, p), dist(r2, p));
  129.     }
  130.    
  131.     template <class G> bool
  132.     has (G g, Point p)
  133.     { return eq(dist(g, p), 0); }
  134.    
  135.     Point intersect (Segment a, Segment b) {
  136.         Line la(a), lb(b);
  137.         Point p = intersect(la, lb);
  138.         if (p == POINTS) {
  139.             // Return one of that points.
  140.             if (has(a, b.p)) return b.p;
  141.             if (has(a, b.q)) return b.q;
  142.             if (has(b, a.p)) return a.p;
  143.             if (has(b, a.q)) return a.q;
  144.                                                                         assert(false);
  145.         } else if (p != NO_POINT && has(a, p) && has(b, p)) {
  146.             return p;
  147.         } else
  148.             return NO_POINT;
  149.     }
  150. }
  151.  
  152.  
  153. namespace circleGeometry {
  154.     using namespace floatGeometry;
  155.     typedef pair<Point, Point> twoPoints;
  156.     struct Circle { Point O; ld r; };
  157.    
  158.     istream &operator>> (istream &s, Circle &c)
  159.     { return s >> c.O >> c.r; }
  160.     ostream &operator<< (ostream &s, Circle c)
  161.     { return s << c.O << "  " << c.r; }
  162.    
  163.     twoPoints intersect (Circle c, Line l) {
  164.         ld d = dist(l, c.O);                                            //addlog("dist =", d);
  165.         if (c.r < d - eps) return {NO_POINT, NO_POINT};                
  166.         ld L = sqrt( c.r * c.r - d * d );
  167.         Vector perL{ l.a, l.b };
  168.         Vector OH = perL * (d / abs(perL));
  169.         Point H = c.O + OH; if (!has(l, H)) H = c.O - OH;               assert(has(l, H)); // ????
  170.         Vector parL = turn90(perL);
  171.         Vector dH = parL * (L / abs(parL));
  172.         twoPoints res = {H + dH, H - dH};
  173.         if (eq(c.r, d)) {
  174.             assert(res.first == res.second);
  175.             res.first = NO_POINT;
  176.         } return res;
  177.     }
  178.    
  179.     Point _check (Point p, Segment s) {
  180.         if (p == NO_POINT || p == POINTS || has(s, p)) return p;
  181.         return NO_POINT;
  182.     }
  183.    
  184.     twoPoints intersect (Circle c, Segment s) {
  185.         Line l(s);
  186.         twoPoints tp = intersect(c, l);
  187.         twoPoints res{ _check(tp.first, s), _check(tp.second, s) };
  188.         if (res.second == NO_POINT) swap(res.first, res.second);
  189.         return res;
  190.     }
  191. }
  192.  
  193.  
  194.  
  195.  
  196. using namespace circleGeometry;
  197. int main () {
  198.    
  199.     for (Vector a, b; cin >> a >> b; )
  200.         pcout << ang(a, b) << endl;
  201.    
  202.     return 0;
  203. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement