Advertisement
Guest User

Untitled

a guest
Oct 31st, 2014
152
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 5.74 KB | None | 0 0
  1. #include <iostream>
  2. #include <cmath>
  3.  
  4. using std::cout;
  5. using std::cin;
  6. using std::endl;
  7. using std::abs;
  8.  
  9. class fraction {
  10.  private:
  11.     long long int num, den;  //  num/den
  12.  
  13.     static long long int gcd(long long int a, long long int b) {
  14.         return (b != 0) ? gcd(b, a % b) : a;
  15.     }
  16.  
  17.  public:
  18.     fraction() : num(0), den(1) {}
  19.     fraction(long long int n, long long int d) {
  20.         num = n / gcd(abs(n), abs(d));
  21.         den = d / gcd(abs(n), abs(d));
  22.     }
  23.  
  24.     const long long int getNum() const {
  25.         return num;
  26.     }
  27.  
  28.     const long long int getDen() const {
  29.         return den;
  30.     }
  31.  
  32.     const fraction operator+ (fraction other) const {
  33.         long long int newNum, newDen;
  34.         newNum = num * other.getDen() + other.getNum() * den;
  35.         newDen = den * other.getDen();
  36.         return fraction(newNum, newDen);
  37.     }
  38.  
  39.     const fraction operator- (fraction other) const {
  40.         long long int newNum, newDen;
  41.         newNum = num * other.getDen() - other.getNum() * den;
  42.         newDen = den * other.getDen();
  43.         return fraction(newNum, newDen);
  44.     }
  45.  
  46.     const fraction operator* (fraction other) const {
  47.         return fraction(num * other.getNum(), den * other.getDen());
  48.     }
  49.  
  50.     const fraction operator/ (fraction other) const {
  51.         return fraction(num * other.getDen(), den * other.getNum());
  52.     }
  53.  
  54.     const bool operator== (fraction other) const {
  55.         return (num == other.getNum()) && (den == other.getDen());
  56.     }
  57.  
  58.     const bool operator> (fraction other) const {
  59.         return num * other.getDen() > other.getNum() * den;
  60.     }
  61.  
  62.     const bool operator< (fraction other) const {
  63.         return num * other.getDen() < other.getNum() * den;
  64.     }
  65.  
  66.     const long long int sign() const {
  67.         if (num * den > 0) {
  68.             return 1;
  69.         } else {
  70.             return -1;
  71.         }
  72.     }
  73. };
  74.  
  75. struct point {
  76.     fraction x, y;
  77.     bool err;
  78.     point() {
  79.         err = false;
  80.     }
  81.     point(long long int xx, long long int yy) {
  82.         x = fraction(xx, 1);
  83.         y = fraction(yy, 1);
  84.         err = false;
  85.     }
  86. };
  87.  
  88. class line {
  89.  private:
  90.     fraction k, b;  // y = kx + b
  91.     bool vertical;
  92.     fraction x;  // x = a
  93.  
  94.  public:
  95.     line() : k(fraction()), b(fraction()), vertical(false), x(fraction()) {}
  96.     line(long long int x1, long long int y, long long int q, long long int w) {
  97.         vertical = (x1 == q);
  98.         x = fraction(x1, 1);
  99.         k = fraction(y - w, x1 - q);
  100.         b = fraction(y, 1) - k * fraction(x1, 1);
  101.     }
  102.  
  103.     const fraction getK() const {
  104.         return k;
  105.     }
  106.  
  107.     const fraction getB() const {
  108.         return b;
  109.     }
  110.  
  111.     const bool isVertical() const {
  112.         return vertical;
  113.     }
  114.  
  115.     const fraction getX() const {
  116.         return x;
  117.     }
  118.  
  119.     bool operator== (const line &other) const {
  120.         if (other.isVertical() && vertical) {
  121.             return (x == other.getX());
  122.         }
  123.         return (k == other.getK()) && (b == other.getB());
  124.     }
  125.  
  126.     point intersection(const line &other) {
  127.         point result;
  128.         if (vertical) {
  129.             if ( other.isVertical() && !(other.getX() == x) ) {
  130.                 result.err = true;
  131.                 return result;
  132.             }
  133.             result.x = x;
  134.             result.y = other.getK() * x + other.getB();
  135.             return result;
  136.         }
  137.  
  138.         if (other.isVertical()) {
  139.             if ( vertical && !(other.getX() == x) ) {
  140.                 result.err = true;
  141.                 return result;
  142.             }
  143.             result.x = other.getX();
  144.             result.y = k * other.getX() + b;
  145.             return result;
  146.         }
  147.  
  148.         if (k == other.getK()) {
  149.             result.err = true;
  150.             return result;
  151.         }
  152.         result.x = (other.getB() - b) / (k - other.getK());
  153.         result.y = k * result.x + b;
  154.         return result;
  155.     }
  156.  
  157.     bool belong(point p) {
  158.         if (vertical) {
  159.             return (p.x == x);
  160.         }
  161.         return (p.y == k * p.x + b);
  162.     }
  163. };
  164.  
  165. bool onOneSide(const point &center, const point &one, const point &two) {
  166.     bool r = true;
  167.     r = r && (one.x - center.x).sign() == (two.x - center.x).sign();
  168.     r = r && (one.y - center.y).sign() == (two.y - center.y).sign();
  169.     return r;
  170. }
  171.  
  172. int main() {
  173.     long long int x1, y1, x2, y2;
  174.     cin >> x1 >> y1 >> x2 >> y2;
  175.     line first(x1, y1, x2, y2);  // первая прямая
  176.     cin >> x1 >> y1 >> x2 >> y2;
  177.     line second(x1, y1, x2, y2);
  178.     // луч,однако по факту это таже прямая,только обрубленная в какой-то точке
  179.  
  180.     if ((first == second) || (first.belong(point(x1, y1)))) {
  181.         cout << "YES" << endl;
  182.     } else {
  183.         point beginBeam(x1, y1), secondBeam(x2, y2), inter;
  184.         inter = first.intersection(second);
  185.         // beginBeam - это как раз та "какая-то" точка, которая "рубит" прямую
  186.         // secondBeam - точка указывающая направление луча
  187.         // inter - точка пересечения прямых
  188.         if (inter.err) {
  189.             cout << "NO" << endl;
  190.             return 0;
  191.         }
  192.  
  193.         if ( onOneSide(beginBeam, secondBeam, inter) ) {
  194.             cout << "YES" << endl;
  195.         } else {
  196.             cout << "NO" << endl;
  197.         }
  198.         // если относительно точки разделения второй прямой точка пересечения
  199.         // находится в части координатной плоскости, где и"направляющая" точка
  200.         // это значит, что луч таки пересек прямую
  201.     }
  202.     return 0;
  203. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement