peltorator

!Integer Geometry

Oct 11th, 2018
212
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. ll sqr(ll a)
  2. {
  3.     return a * a;
  4. }
  5.  
  6.  
  7. /*-----------------------Point-----------------------*/
  8.  
  9. struct Point
  10. {
  11.     ll x, y;
  12.  
  13.     Point():
  14.         x(0),
  15.         y(0) {}
  16.     Point(ll x, ll y):
  17.         x(x),
  18.         y(y) {}
  19.  
  20.     Point operator-() const
  21.     {
  22.         return Point(-x, -y);
  23.     }
  24.  
  25.     Point operator+(const Point &a) const
  26.     {
  27.         return Point(a.x + x, a.y + y);
  28.     }
  29.  
  30.     void operator+=(const Point &a)
  31.     {
  32.         x += a.x;
  33.         y += a.y;
  34.     }
  35.  
  36.     Point operator-(const Point &a) const
  37.     {
  38.         return Point(x - a.x, y - a.y);
  39.     }
  40.  
  41.     void operator-=(const Point &a)
  42.     {
  43.         x -= a.x;
  44.         y -= a.y;
  45.     }
  46.  
  47.     ll operator^(const Point &a) const
  48.     {
  49.         return x * a.y - y * a.x;
  50.     }
  51.  
  52.     ll operator*(const Point &a) const
  53.     {
  54.         return x * a.x + y * a.y;
  55.     }
  56.  
  57.     Point operator*(const ll &a) const
  58.     {
  59.         return Point(x * a, y * a);
  60.     }
  61.  
  62.     friend Point operator*(const ll &a, const Point &p);
  63.  
  64.     void operator*=(const ll &a)
  65.     {
  66.         x *= a;
  67.         y *= a;
  68.     }
  69.  
  70.     ll lensqr() const
  71.     {
  72.         return x * x + y * y;
  73.     }
  74.  
  75.     bool operator<(const Point &a) const
  76.     {
  77.         return y < a.y || (y == a.y && x < a.x);
  78.     }
  79.  
  80.     bool operator>(const Point &a) const
  81.     {
  82.         return y > a.y || (y == a.y && x > a.x);
  83.     }
  84.  
  85.     bool operator==(const Point &a) const
  86.     {
  87.         return a.x == x && a.y == y;
  88.     }
  89.  
  90.     bool operator!=(const Point &a) const
  91.     {
  92.         return x != a.x || y != a.y;
  93.     }
  94.  
  95.     Point operator=(const Point &a)
  96.     {
  97.         x = a.x;
  98.         y = a.y;
  99.         return (*this);
  100.     }
  101.  
  102.     void read()
  103.     {
  104.         ll a, b;
  105.         cin >> a >> b;
  106.         x = a;
  107.         y = b;
  108.     }
  109.  
  110.     void write() const
  111.     {
  112.         cout << x << ' ' << y << '\n';
  113.     }
  114.  
  115.     void debwrite() const
  116.     {
  117. #ifdef ONPC
  118.         cerr << "       point: x = " << x << ", y = " << y << endl;
  119. #endif
  120.     }
  121.  
  122.     Point rotate() const
  123.     {
  124.         return Point(-y, x);
  125.     }
  126.  
  127.     bool is_zero() const
  128.     {
  129.         return x == 0 && y == 0;
  130.     }
  131. };
  132.  
  133. Point operator*(const ll &a, const Point &p)
  134. {
  135.     return Point(a * p.x, a * p.y);
  136. }
  137.  
  138. ll distsqr(const Point &a, const Point &b)
  139. {
  140.     return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
  141. }
  142.  
  143.  
  144.  
  145. ll gcd(ll a, ll b)
  146. {
  147.     while (a)
  148.     {
  149.         b %= a;
  150.         swap(a, b);
  151.     }
  152.     return b;
  153. }
  154.  
  155.  
  156. /*-----------------------------------------Line--------------------------*/
  157.  
  158.  
  159. struct Line
  160. {
  161.     ll a, b, c;
  162.  
  163.     Line():
  164.         a(1),
  165.         b(1),
  166.         c(0) {}
  167.  
  168.     Line(ll a, ll b, ll c):
  169.         a(a),
  170.         b(b),
  171.         c(c) {}
  172.  
  173.     Line(Point a, Point b):
  174.         a(a.y - b.y),
  175.         b(b.x - a.x),
  176.         c((b.y - a.y) * a.x + (a.x - b.x) * a.y) {}
  177.  
  178.     ll lensqr() const
  179.     {
  180.         return a * a + b * b;
  181.     }
  182.  
  183.     ll operator()(const Point &p) const
  184.     {
  185.         return a * p.x + b * p.y + c;
  186.     }
  187.  
  188.     void norm()
  189.     {
  190. #ifdef ONPC
  191.         if (a == 0 && b == 0)
  192.             assert("norming strange (0, 0, c) line");
  193. #endif
  194.         ll x = gcd(a, gcd(b, c));
  195.         a /= x;
  196.         b /= x;
  197.         c /= x;
  198.         if (a < 0 || (a == 0 && b < 0))
  199.         {
  200.             a = -a;
  201.             b = -b;
  202.             c = -c;
  203.         }
  204.     }
  205.  
  206.     bool parallel(const Line &l) const
  207.     {
  208.         return l.a * b == l.b * a;
  209.     }
  210.  
  211.     bool lies(const Point &p) const
  212.     {
  213.         return a * p.x + b * p.y + c == 0;
  214.     }
  215.  
  216.     Line perpendicular() const
  217.     {
  218.         return Line(-b, a, 0);
  219.     }
  220.  
  221.     Line perpendicular(const Point &p) const
  222.     {
  223.         return Line(-b, a, p.x * b - p.y * a);
  224.     }
  225.  
  226.     void read()
  227.     {
  228.         ll x, y, z;
  229.         cin >> x >> y >> z;
  230.         a = x;
  231.         b = y;
  232.         c = z;
  233.     }
  234.  
  235.     void write()
  236.     {
  237.         cout << a << ' ' << b << ' ' << c << '\n';
  238.     }
  239.  
  240.     void debwrite() const
  241.     {
  242. #ifdef ONPC
  243.         cerr << "       line: a = " << a << ", b = " << b << ", c = " << c << endl;
  244. #endif
  245.     }
  246.  
  247. };
  248.  
  249. bool parallel(Line l, Line k)
  250. {
  251.     return l.a * k.b == l.b * k.a;
  252. }
  253.  
  254. bool point_on_line(Point p, Line l)
  255. {
  256.     return p.x * l.a + p.y * l.b + l.c == 0;
  257. }
  258.  
  259. bool point_on_line(Point p, Point a, Point b)
  260. {
  261.     return point_on_line(p, Line(a, b));
  262. }
  263.  
  264. bool point_on_line(Line l, Point p)
  265. {
  266.     return p.x * l.a + p.y * l.b + l.c == 0;
  267. }
  268.  
  269. bool three_points_on_line(Point a, Point b, Point c)
  270. {
  271.     return ((a - b) ^ (b - c)) == 0;
  272. }
  273.  
  274. bool collinear(Point a, Point b, Point c)
  275. {
  276.     return ((a - b) ^ (b - c)) == 0;
  277. }
  278.  
  279. Line perp(Point p, Line l)
  280. {
  281.     return Line(-l.b, l.a, p.x * l.b - p.y * l.a);
  282. }
  283.  
  284. Line perp(Line l, Point p)
  285. {
  286.     return Line(-l.b, l.a, p.x * l.b - p.y * l.a);
  287. }
  288.  
  289. bool point_on_ray(Point p, Point a, Point b)
  290. {
  291.     if ((b - a) * (p - a) >= 0)
  292.     {
  293.         Line l(a, b);
  294.         return point_on_line(p, l);
  295.     }
  296.     return 0;
  297. }
  298.  
  299. bool point_on_segment(Point p, Point a, Point b)
  300. {
  301.     return point_on_ray(p, a, b) && point_on_ray(p, b, a);
  302. }
  303.  
  304. bool point_in_angle(Point P, Point A, Point O, Point B)
  305. {
  306.     P -= O;
  307.     A -= O;
  308.     B -= O;
  309.     if ((B ^ A) > 0)
  310.         swap(A, B);
  311.     return (A ^ P) >= 0 && (P ^ B) >= 0;
  312. }
  313.  
  314. ll double_area(vector<Point> p)
  315. {
  316.     ll s = 0;
  317.     int n = p.size();
  318.     for (int i = 0; i < n; i++)
  319.     {
  320.         int j = (i + 1) % n;
  321.         s += (p[i].x - p[j].x) * (p[i].y + p[j].y);
  322.     }
  323.     return abs(s);
  324. }
  325.  
  326. bool point_in_convex_polygon(Point A, vector<Point> p)
  327. {
  328.     int n = p.size();
  329.     for (int i = 0; i < n; i++)
  330.     {
  331.         int j = (i + 1) % n, k = (i + 2) % n;
  332.         Line l = Line(p[i], p[j]);
  333.         if (l(A) * l(p[k]) < 0)
  334.             return 0;
  335.     }
  336.     return 1;
  337. }
  338.  
  339.  
  340. bool where(Point v)
  341. {
  342.     if (v.y != 0)
  343.         return v.y > 0;
  344.     return v.x > 0;
  345. }
  346.  
  347. bool convex_hull_cmp(Point v, Point u)
  348. {
  349.     if (u.is_zero())
  350.         return 0;
  351.     if (v.is_zero())
  352.         return 1;
  353.     bool x = where(v), y = where(u);
  354.     if (x != y)
  355.         return x;
  356.     ll t = (v ^ u);
  357.     if (t != 0)
  358.         return t > 0;
  359.     return v.lensqr() < u.lensqr();
  360. }
  361.  
  362. vector<Point> graham_convex_hull(vector<Point> a)
  363. {
  364.     int n = a.size();
  365.     Point down = a[0];
  366.     for (int i = 1; i < n; i++)
  367.         if (a[i] < down)
  368.             down = a[i];
  369.     for (int i = 0; i < n; i++)
  370.         a[i] -= down;
  371.     sort(a.begin(), a.end(), convex_hull_cmp);
  372.     vector<Point> v;
  373.     for (int i = 0; i < n; i++)
  374.     {
  375.         while (v.size() > 1 && ((a[i] - v.back()) ^ (v.back() - v[v.size() - 2])) >= 0)
  376.             v.pop_back();
  377.         v.push_back(a[i]);
  378.     }
  379.     for (int i = 0; i < (int)v.size(); i++)
  380.         v[i] += down;
  381.     return v;
  382. }
  383.  
  384. vector<Point> jarvis_convex_hull(vector<Point> a)
  385. {
  386.     int n = a.size();
  387.     if (n < 2)
  388.         return a;
  389.     if (n == 2)
  390.     {
  391.         if (a[0] == a[1])
  392.             return {a[0]};
  393.         return a;
  394.     }
  395.     Point down = a[0];
  396.     int k = 0;
  397.     for (int i = 0; i < n; i++)
  398.         if (a[i] < down)
  399.             k = i, down = a[i];
  400.     vector<Point> v;
  401.     v.push_back(down);
  402.     int cur = k;
  403.     while (true)
  404.     {
  405.         int next = -1;
  406.         for (int i = 0; i < n; i++)
  407.             if (i != cur && (next == -1 || ((a[i] - a[cur]) ^ (a[next] - a[cur])) > 0 ||
  408.             (((a[i] - a[cur]) ^ (a[next] - a[cur])) == 0 && (a[i] - a[cur]).lensqr() > (a[next] - a[cur]).lensqr())))
  409.                 next = i;
  410.         if (next == k)
  411.             break;
  412.         v.push_back(a[next]);
  413.         cur = next;
  414.     }
  415.     return v;
  416. }
  417.  
  418. vector<Point> sum(vector<Point> a, vector<Point> b)
  419. {
  420.     vector<Point> v, vect;
  421.     v.clear();
  422.     vect.clear();
  423.     int n = a.size();
  424.     int m = b.size();
  425.     Point besta(5e18, 5e18);
  426.     for (int i = 0; i < n; i++)
  427.         if (a[i] < besta)
  428.             besta = a[i];
  429.     Point bestb(5e18, 5e18);
  430.     for (int i = 0; i < m; i++)
  431.         if (b[i] < bestb)
  432.             bestb = b[i];
  433.     Point start = besta + bestb;
  434.     for (int i = 0; i < n; i++)
  435.         vect.push_back(a[(i + 1) % n] - a[i]);
  436.     for (int i = 0; i < m; i++)
  437.         vect.push_back(b[(i + 1) % m] - b[i]);
  438.     sort(vect.begin(), vect.end(), convex_hull_cmp);
  439.     for (int i = 0; i < (int)vect.size(); i++)
  440.     {
  441.         start += vect[i];
  442.         v.push_back(start);
  443.     }
  444.     return v;
  445. }
  446.  
  447. bool ray_ray_intersect(Point x, Point y, Point p, Point q)
  448. {
  449.     if (point_on_ray(x, p, q) || point_on_ray(y, p, q) || point_on_ray(p, x, y) || point_on_ray(q, x, y))
  450.         return true;
  451.     if (point_on_line(x, p, q) || point_on_line(y, p, q))
  452.         return false;
  453.     Line l(x, y), k(p, q);
  454.     if (parallel(l, k))
  455.         return false;
  456.     ll a = k.c * l.b - l.c * k.b;
  457.     ll b = l.a * k.b - k.a * l.b;
  458.     ll c = k.a * l.c - l.a * k.c;
  459.     ll d = b;
  460.     if (b < 0)
  461.     {
  462.         a = -a;
  463.         b = -b;
  464.         c = -c;
  465.         d = -d;
  466.     }
  467.     y -= x;
  468.     q -= p;
  469.     bool A = 1, B = 1, C = 1, D = 1;
  470.     if (y.x < 0 || (y.x == 0 && y.y < 0))
  471.         A = 0;
  472.     if (q.x < 0 || (q.x == 0 && q.y < 0))
  473.         C = 0;
  474.     if (a < b * x.x || (a == b * x.x && c < d * x.y))
  475.         B = 0;
  476.     if (a < b * p.x || (a == b * p.x && c < d * p.y))
  477.         D = 0;
  478.     bool fir = (A == B), sec = (C == D);
  479.     return fir && sec;
  480. }
  481.  
  482. bool rays_intersect(Point x, Point y, Point p, Point q)
  483. {
  484.     return ray_ray_intersect(x, y, p, q);
  485. }
  486.  
  487. bool segment_ray_intersect(Point x, Point y, Point p, Point q)
  488. {
  489.     return ray_ray_intersect(x, y, p, q) && ray_ray_intersect(y, x, p, q);
  490. }
  491.  
  492. bool ray_segment_intersect(Point p, Point q, Point x, Point y)
  493. {
  494.     return segment_ray_intersect(x, y, p, q);
  495. }
  496.  
  497. bool segment_segment_intersect(Point x, Point y, Point p, Point q)
  498. {
  499.     return segment_ray_intersect(x, y, p, q) && segment_ray_intersect(x, y, q, p);
  500. }
  501.  
  502. bool segments_intersect(Point x, Point y, Point p, Point q)
  503. {
  504.     return segment_segment_intersect(x, y, p, q);
  505. }
  506.  
  507. /*                     Functions:
  508.  *
  509.  * sqr(ll a) = a^2
  510.  * distsqr(Point a, Point b) = d(a, b)^2
  511.  * gcd(a, b)
  512.  *
  513.  *
  514.  *                     Points:
  515.  * Point() = (0, 0)
  516.  * Point(x, y) = (x, y)
  517.  * -Point
  518.  * Point + Point
  519.  * Point += Point
  520.  * Point - Point
  521.  * Point -= Point
  522.  * Point ^ Point = vect product
  523.  * Point * Point = scal product
  524.  * Point * ll
  525.  * ll * Point
  526.  * Point *= ll
  527.  * lensqr() == len of vector
  528.  * operator<
  529.  * operator>
  530.  * operator==
  531.  * operator!=
  532.  * operator=
  533.  * read (x, y)
  534.  * write (x y\n)
  535.  * debwrite cerr (         point: x = ..., y = ...endl)
  536.  * rotate (-y, x)
  537.  * is_zero (0, 0)?
  538.  *
  539.  *
  540.  *
  541.  *                  Lines:
  542.  * Line() = (1, 1, 0)
  543.  * Line(a, b, c) = (a, b, c)
  544.  * Line(Point a, Point b) = a, b on line
  545.  * lensqr() = a * a + b * b
  546.  * operator()(Point) = ax + by + c
  547.  * norm = /=gcd. equal lines are now equal. assertion ifdef ONPC
  548.  * parallel(line) = parallel or equal
  549.  * lies(Point)
  550.  * perpendicular() = (-b, a, 0)
  551.  * perpendicular(Point) = (-b, a, bx - ay)
  552.  * read (a, b, c)
  553.  * write (a b c\n)
  554.  * debwrite cerr (       line: a = ..., b = ..., c = ...endl)
  555.  *
  556.  *
  557.  *                 Standart:
  558.  * parallel(Line, Line) = parallel or equal
  559.  * point_on_line(Point, Line) or (Line, Point)
  560.  * three_points_on_line = collinear(a, b, c)
  561.  * perp(Line, Point) or (Point, Line) = Line.perpendicular(Point)
  562.  * point_on_ray(p, l, r) = not strictly
  563.  * point_on_segment(p, l, r) = not strictly
  564.  * point_in_angle(p, a, o, b) = not strictly
  565.  * double_area(vector<Point>) = sqr * 2 (sqr can be not int)
  566.  * point_in_convex_polygon(Point, vector<Point>) = not strictly
  567.  * graham_convex_hull = no collinear points
  568.  * jarvis_convex_hull = no collinear points
  569.  * sum(vector<Point>, vector<Point>) = sum of polygons
  570.  * bool segment_ray_intersect(x, y, p, q) = [x, y], [p, q) ????????
  571.  * bool ray_segment_intersect(p, q, x, y) = [x, y], [p, q) ????????
  572.  * segment_segment_intersect = segments_intersect(x, y, p, q) = [x, y], [p, q]
  573.  *
  574.  *
  575.  */
  576.  
  577. ///ADD ostream, istream, ray_ray_intersect
RAW Paste Data