Advertisement
Guest User

Untitled

a guest
Jan 21st, 2020
93
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 8.58 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4. #include <algorithm>
  5. #include <cmath>
  6. #include <utility>
  7.  
  8. using namespace std;
  9.  
  10. double sqr(double a) // квадрат числа
  11. {
  12. return a * a;
  13. }
  14.  
  15.  
  16. bool doubleEqual(double a, double b) // сравниваем на равенство с eps, константой 1е-9 используется только здесь
  17. {
  18. return fabs(a - b) < 1e-9;
  19. }
  20.  
  21.  
  22. bool doubleLessOrEqual(double a, double b) // <= с eps
  23. {
  24. return a < b || doubleEqual(a, b);
  25. }
  26.  
  27.  
  28. bool doubleLess(double a, double b) // < с eps
  29. {
  30. return a < b && !doubleEqual(a, b);
  31. }
  32.  
  33.  
  34. bool doubleGreaterOrEqual(double a, double b) // >= с eps
  35. {
  36. return a > b || doubleEqual(a, b);
  37. }
  38.  
  39.  
  40. bool doubleGreater(double a, double b) // > с eps
  41. {
  42. return a > b && !doubleEqual(a, b);
  43. }
  44.  
  45.  
  46. double mySqrt(double a) // mySqrt с проверкой, что корректен аргумент
  47. {
  48. if(doubleLess(a, 0) ) //некорректный вызов
  49. {
  50. throw "sqrt(-1)";
  51. }
  52. if(a < 0) return 0; //отрицательное ввиду небольшой погрешности
  53. return sqrt(a);
  54. }
  55.  
  56.  
  57. struct Point{ // класс точки или вектора, далее мы эти понятия разделять не будем
  58. // но условимся (для удобного чтения) большими буквами обозначать точки (A, B, C, D, ...)
  59. // маленькими - вектора(v, u, w,...)
  60. double x, y; // 2 приватных поля, других не будет
  61. Point(): x(0), y(0) {} // конструктор по умолчанию
  62.  
  63. Point(double x, double y): x(x), y(y) {} // намеренно сделаем два конструктора вместо Point(x = 0...)
  64. //Это избавит нас от ошибок вида Point A = 2;
  65.  
  66. void scan() // читаем координаты точки
  67. {
  68. scanf("%lf %lf", &x, &y);
  69. }
  70.  
  71. void print() const // выводим координаты точки
  72. {
  73. printf("%.10lf %.10lf\n", x, y);
  74. }
  75.  
  76. Point operator+(const Point & p) const // сложение 2х векторов
  77. {
  78. return Point(x + p.x, y + p.y);
  79. }
  80.  
  81. Point operator-(const Point & p) const // вычитание 2х векторов
  82. {
  83. return Point(x - p.x, y - p.y);
  84. }
  85.  
  86. Point operator-() const // обратный вектор
  87. {
  88. return Point(-x, -y);
  89. }
  90.  
  91. Point operator*(double k) const // умножение вектора на скаляр
  92. {
  93. return Point(x * k, y * k);
  94. }
  95.  
  96. Point operator/(double k) const // деление вектора на скаляр
  97. {
  98. return Point(x / k, y / k);
  99. }
  100.  
  101. double operator%(const Point & p) const // скалярное произведение
  102. {
  103. return x * p.x + y * p.y;
  104. }
  105.  
  106. double operator*(const Point & p) const // векторное произведение
  107. {
  108. return x * p.y - y * p.x;
  109. }
  110.  
  111. double length() const // длина вектора по определению из ан.гема (корень из скалярного квадрата)
  112. {
  113. return mySqrt(*this % *this);
  114. }
  115.  
  116. double distTo(const Point & p) const //расстояние между 2мя точками - модуль вектора между ними
  117. {
  118. return (*this - p).length();
  119. }
  120.  
  121. double distTo(const Point & A, const Point & B) const // расстояние от точки до прямой (всегда >= 0)
  122. {
  123. double d = A.distTo(B);
  124. if(doubleEqual(d, 0) ) // прямая должна задаваться двумя! точками
  125. {
  126. throw "A = B";
  127. }
  128. double s = (*this - A) * (*this - B); // удвоенная площадь треугольника
  129. return fabs(s) / d; // метод площадей
  130. }
  131.  
  132. Point normalize(double k = 1) const // выставляет длину вектора в k
  133. {
  134. double len = length(); // Текущая длина
  135. if(doubleEqual(len, 0) ) // если длина ноль
  136. {
  137. if(doubleEqual(k, 0) )
  138. {
  139. return Point();
  140. }
  141. throw "zero-size vector"; //кроме нулевой никакую получить не можем
  142. }
  143. return *this * (k / len);
  144. }
  145.  
  146. Point getH(const Point & A, const Point & B) const // опускаем высоту из точки на прямую (A, B)
  147. {
  148. Point C = *this;
  149. Point v = B - A; // направляющий вектор прямой
  150. Point u = C - A; // вектор, проекция которого нам нужна
  151. double k = v % u / v.length(); // нашли длину проекции
  152. v = v.normalize(k); // нашли проекцию u на v
  153. Point H = A + v; // подвинули точку A в проекцию конца вектора u, отложенного из A
  154. return H;
  155. }
  156.  
  157. Point rotate() const // поворот на 90 градусов против часовой стрелки (положительное направление)
  158. {
  159. return Point(-y, x);
  160. }
  161.  
  162. Point rotate(double alpha) const // поворот на угол alpha против часовой стрелки
  163. // (по часовой стрелке, если alpha < 0)
  164. {
  165. return rotate(cos(alpha), sin(alpha) ); // делегируем задачу другому экземпляру функции
  166. }
  167.  
  168. Point rotate(double cosa, double sina) const // поворот с заданными косинусом и синусом
  169. {
  170. Point v = *this;
  171. Point u = v.rotate(); // вектор, перпендикулярный v, теперь (v, u) - базис, в котором мы знаем ответ
  172. Point w = v * cosa + u * sina; // зная координаты в базисе (v, u), нашли w
  173. return w;
  174. }
  175.  
  176. bool isZero() const // проверка на то, что точка нулевая без сложных операций и погрешности
  177. {
  178. return doubleEqual(x, 0) && doubleEqual(y, 0);
  179. }
  180.  
  181. bool isOnLine(const Point & A, const Point & B) const // точка на прямой?
  182. {
  183. return doubleEqual( (A - *this) * (B - *this), 0);
  184. }
  185.  
  186. bool isInSegment(const Point & A, const Point & B) const // точка внутри отрезка?
  187. {
  188. return isOnLine(A, B) && doubleLessOrEqual( (A - *this) % (B - *this), 0 );
  189. }
  190.  
  191. bool isInSegmentStrictly(const Point & A, const Point & B) const // точка внутри отрезка строго?
  192. {
  193. return isOnLine(A, B) && doubleLess( (A - *this) % (B - *this), 0 );
  194. }
  195.  
  196. double getAngle() const
  197. {
  198. return atan2(y, x); // угол между вектором и осью ОХ
  199. }
  200.  
  201. double getAngle(Point u) const
  202. {
  203. Point v = *this;
  204. return atan2(v * u, v % u); // ориентированный угол между векторами
  205. }
  206.  
  207. };
  208.  
  209. int getIntersection // ищем пересечение прямой (A, B) и прямой (C, D)
  210. (
  211. const Point & A,
  212. const Point & B,
  213. const Point & C,
  214. const Point & D,
  215. Point & O
  216. )
  217. {
  218. Point v = B - A; // направляющий вектор прямой (A, B)
  219. double s1 = (C - A) * (D - A); // площадь треугольника A, C, D
  220. double s2 = (D - B) * (C - B); // площадь треугольника B, D, C
  221. double s = s1 + s2; // площадь четурёхугольника
  222. if(doubleEqual(s, 0) ) // прямые параллельны (или совпадают)
  223. {
  224. if(!A.isOnLine(C, D) ) // прямые параллельны
  225. {
  226. return 0; // пересечение пусто
  227. }
  228. return 2; // больше 1ой точки в пересечении
  229. }
  230. v = v / s;
  231. v = v * s1; // вектора AO и AB пропорциональны площадям s1 и s
  232. O = A + v; // нашли точку пересечения
  233. return 1; // 1 точка в пересечении
  234. }
  235.  
  236. int main(){
  237. Point o, a, b;
  238. o.scan();
  239. a.scan();
  240. b.scan();
  241. if(o.isInSegment(a, b)){
  242. cout << "YES";
  243. }
  244. else{
  245. cout << "NO";
  246. }
  247.  
  248. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement