fork download
copy 
  1. #include <algorithm>    // for std::sort
  2. #include <iostream>
  3. #include <vector>
  4. #include <math.h>       // for sqrt
  5.  
  6. //////////////////////////////////////////////////////////////////////
  7.  
  8. class Vec2F {
  9.   public:
  10.     float x, y;
  11.     static const Vec2F ORIGIN, I, J;
  12.  
  13.     Vec2F() : x(0), y(0) {}
  14.     Vec2F(float x, float y) : x(x), y(y) {}
  15.     Vec2F(const Vec2F &other) : x(other.x), y(other.y) {}
  16.     Vec2F &operator=(const Vec2F &other) {
  17.         if (this != &other) {
  18.             x = other.x;
  19.             y = other.y;
  20.         }
  21.         return *this;
  22.     }
  23.     bool operator==(const Vec2F &other) const {
  24.         return x == other.x && y == other.y;
  25.     }
  26.     const Vec2F operator+(const Vec2F &other) const {
  27.         return Vec2F(x + other.x, y + other.y);
  28.     }
  29.     Vec2F operator-() const {
  30.         return Vec2F(-x, -y);
  31.     }
  32.     Vec2F operator-(const Vec2F &other) const {
  33.         return *this + -other;
  34.     }
  35.     Vec2F operator*(float scale) const {
  36.         return Vec2F(scale * x, scale * y);
  37.     }
  38.     float cross(const Vec2F &other) const {
  39.         return x * other.y - y * other.x;
  40.     }
  41.     float dot(const Vec2F &other) const {
  42.         return x * other.x + y * other.y;
  43.     }
  44.     float magnitude() const {
  45.         return sqrt(x * x + y * y);
  46.     }
  47.     float sinOfAngleRelTo(const Vec2F &ref) const {
  48.         return ref.cross(*this) / ref.magnitude() / this->magnitude();
  49.     }
  50.     float cosOfAngleRelTo(const Vec2F &ref) const {
  51.         return ref.dot(*this) / ref.magnitude() / this->magnitude();
  52.     }
  53.     friend std::ostream &operator<<(std::ostream &out, const Vec2F &v) {
  54.         return out << '(' << v.x << ", " << v.y << ')';
  55.     }
  56. };
  57.  
  58. const Vec2F Vec2F::ORIGIN(0, 0),
  59.             Vec2F::I(1, 0),
  60.             Vec2F::J(0, 1);
  61.  
  62. //////////////////////////////////////////////////////////////////////
  63.  
  64. class Block {
  65.   public:
  66.     const std::vector<Vec2F> vertices;
  67.  
  68.     // Block is specified by its southwest corner
  69.     Block(const Vec2F &sw) {
  70.         Vec2F v[] = {
  71.             sw + Vec2F::J,      sw + Vec2F(1, 1),
  72.             sw,                 sw + Vec2F::I,
  73.         };
  74.         const_cast<std::vector<Vec2F>& >(vertices) =
  75.             std::vector<Vec2F>(v, v + sizeof(v) / sizeof(Vec2F));
  76.     }
  77.     Block(const Block &other) : vertices(other.vertices) {}
  78.     friend std::ostream &operator<<(std::ostream &out, const Block &b) {
  79.         return out << "Block<" << b.vertices[2] << " - " << b.vertices[1]
  80.                    << " centered at "
  81.                    << b.vertices[2] + (b.vertices[1] - b.vertices[2]) * 0.5
  82.                    << '>';
  83.     }
  84.   private:
  85.     Block &operator=(const Block &other);
  86. };
  87.  
  88. //////////////////////////////////////////////////////////////////////
  89.  
  90. // Comparator for Vec2F to be used to sort points by how much their angle
  91. // deviates from a reference vector
  92. class AxisComparator {
  93.   public:
  94.     static const AxisComparator HORIZ, VERT;
  95.     const Vec2F ref;
  96.  
  97.     AxisComparator(const Vec2F &ref) : ref(ref) {}
  98.  
  99.     // Returns true if a should be ordered before b
  100.     bool operator()(const Vec2F &a, const Vec2F &b) const {
  101.         float cosAngleA = a.cosOfAngleRelTo(ref);
  102.         float cosAngleB = b.cosOfAngleRelTo(ref);
  103.         if (cosAngleA == cosAngleB) {
  104.             // Same angle; the longer vector is considered more extreme.
  105.             return cosAngleA < 0 ? a.magnitude() > b.magnitude()
  106.                                  : a.magnitude() < b.magnitude();
  107.         } else {
  108.             return cosAngleA < cosAngleB;
  109.         }
  110.     }
  111.  
  112.     // Returns true if at least some pair of vectors are on opposite sides of
  113.     // ref, or if at least one of them is aligned with ref
  114.     bool straddles(const std::vector<Vec2F> &vv) const {
  115.         int side = 0;
  116.         for (auto i = vv.begin(); i != vv.end(); ++i) {
  117.             float sinAngle = (*i).sinOfAngleRelTo(ref);
  118.             if (sinAngle == 0.0) {                          // aligned with ref
  119.                 return true;
  120.             } else if (side == 0) {                         // 1st time through
  121.                 side = (sinAngle < 0) ? -1 : +1;
  122.             } else if (side == +1 && sinAngle < 0.0) {      // wrong side
  123.                 return true;
  124.             } else if (side == -1 && sinAngle > 0.0) {      // wrong side
  125.                 return true;
  126.             }
  127.         }
  128.         return false;
  129.     }
  130. };
  131.  
  132. const AxisComparator AxisComparator::HORIZ(Vec2F::I),
  133.                      AxisComparator::VERT(Vec2F::J);
  134.  
  135. //////////////////////////////////////////////////////////////////////
  136.  
  137. class Grapple {
  138.   public:
  139.     const Block block;
  140.   private:
  141.     std::vector<Vec2F> vertices;
  142.     const Vec2F *v1, *v2;
  143.  
  144.   public:
  145.     Grapple(const Block &b) : block(b), vertices(b.vertices) {
  146.         if (!AxisComparator::HORIZ.straddles(vertices)) {
  147.             std::sort(vertices.begin(), vertices.end(), AxisComparator::HORIZ);
  148.             v1 = &vertices.front();
  149.             v2 = &vertices.back();
  150.         } else if (!AxisComparator::VERT.straddles(vertices)) {
  151.             std::sort(vertices.begin(), vertices.end(), AxisComparator::VERT);
  152.             v1 = &vertices.front();
  153.             v2 = &vertices.back();
  154.             return;
  155.         } else {
  156.             v1 = v2 = NULL;
  157.         }
  158.     }
  159.     bool possible() const {
  160.         return v1 && v2;
  161.     }
  162.     const Vec2F &vertex1() const {
  163.         return *v1;
  164.     }
  165.     const Vec2F &vertex2() const {
  166.         return *v2;
  167.     }
  168. };
  169.  
  170. //////////////////////////////////////////////////////////////////////
  171.  
  172. int main() {
  173.     Vec2F tests[] = {
  174.         Vec2F(-3.0, -1.0),      // < 9 o'clock
  175.         Vec2F(-3.5, +2.5),      // 10:30
  176.         Vec2F(-0.5, +4.0),      // 12 o'clock
  177.         Vec2F(+2.5, +2.5),      // 1:30
  178.         Vec2F(+4.0, -0.5),      // 3 o'clock
  179.         Vec2F(-0.5, -0.5),      // centered at origin
  180.         Vec2F(+0.0, -0.0),      // corner at origin
  181.     };
  182.     for (int i = 0; i < sizeof(tests) / sizeof(tests[0]); ++i) {
  183.         Block b(tests[i]);
  184.         Grapple g(b);
  185.         if (g.possible()) {
  186.             std::cout << "Grappling vertices for " << g.block << ": " << g.vertex1() << " and " << g.vertex2() << std::endl;
  187.         } else {
  188.             std::cout << g.block << " contains the origin!" << std::endl;
  189.         }
  190.     }
  191.     return 0;
  192. }
Success #stdin #stdout 0s 3444KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Grappling vertices for Block<(-3, -1) - (-2, 0) centered at (-2.5, -0.5)>: (-2, -1) and (-3, 0)
Grappling vertices for Block<(-3.5, 2.5) - (-2.5, 3.5) centered at (-3, 3)>: (-3.5, 2.5) and (-2.5, 3.5)
Grappling vertices for Block<(-0.5, 4) - (0.5, 5) centered at (0, 4.5)>: (-0.5, 4) and (0.5, 4)
Grappling vertices for Block<(2.5, 2.5) - (3.5, 3.5) centered at (3, 3)>: (2.5, 3.5) and (3.5, 2.5)
Grappling vertices for Block<(4, -0.5) - (5, 0.5) centered at (4.5, 0)>: (4, -0.5) and (4, 0.5)
Block<(-0.5, -0.5) - (0.5, 0.5) centered at (0, 0)> contains the origin!
Block<(0, -0) - (1, 1) centered at (0.5, 0.5)> contains the origin!
https://ideone.com/Yqqpo9
http://c...content-available-to-author-only...e.com/q/31597/9357
language:
C++14 (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!