Advertisement
Guest User

Untitled

a guest
Feb 19th, 2018
65
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 12.56 KB | None | 0 0
  1. #pragma GCC optimize("unroll-loops")
  2. #pragma GCC optimize ("Ofast")
  3.  
  4. #define _CRT_SECURE_NO_WARNINGS
  5.  
  6. #include <iostream>
  7. #include <vector>
  8. #include <algorithm>
  9. #include <map>
  10. #include <cmath>
  11.  
  12. using namespace std;
  13.  
  14. //#define int long long
  15. //typedef long long ll;
  16.  
  17. double sqr(double a) // квадрат числа
  18. {
  19. return a * a;
  20. }
  21.  
  22.  
  23. bool doubleEqual(double a, double b) // сравниваем на равенство с eps, константой 1е-9 используется только здесь
  24. {
  25. return fabs(a - b) < 1e-9;
  26. }
  27.  
  28.  
  29. bool doubleLessOrEqual(double a, double b) // <= с eps
  30. {
  31. return a < b || doubleEqual(a, b);
  32. }
  33.  
  34.  
  35. bool doubleLess(double a, double b) // < с eps
  36. {
  37. return a < b && !doubleEqual(a, b);
  38. }
  39.  
  40.  
  41. bool doubleGreaterOrEqual(double a, double b) // >= с eps
  42. {
  43. return a > b || doubleEqual(a, b);
  44. }
  45.  
  46.  
  47. bool doubleGreater(double a, double b) // > с eps
  48. {
  49. return a > b && !doubleEqual(a, b);
  50. }
  51.  
  52.  
  53. double mySqrt(double a) // mySqrt с проверкой, что корректен аргумент
  54. {
  55. if(doubleLess(a, 0) ) //некорректный вызов
  56. {
  57. throw "sqrt(-1)";
  58. }
  59. if(a < 0) return 0; //отрицательное ввиду небольшой погрешности
  60. return sqrt(a);
  61. }
  62.  
  63.  
  64. struct Point{ // класс точки или вектора, далее мы эти понятия разделять не будем
  65. // но условимся (для удобного чтения) большими буквами обозначать точки (A, B, C, D, ...)
  66. // маленькими - вектора(v, u, w,...)
  67. private: double x, y; // 2 приватных поля, других не будет
  68. public:
  69. Point(): x(0), y(0) {} // конструктор по умолчанию
  70.  
  71. Point(double x, double y): x(x), y(y) {} // намеренно сделаем два конструктора вместо Point(x = 0...)
  72. //Это избавит нас от ошибок вида Point A = 2;
  73.  
  74. void scan() // читаем координаты точки
  75. {
  76. scanf("%lf %lf", &x, &y);
  77. }
  78.  
  79. void print() const // выводим координаты точки
  80. {
  81. printf("%.10lf %.10lf\n", x, y);
  82. }
  83.  
  84. Point operator+(const Point & p) const // сложение 2х векторов
  85. {
  86. return Point(x + p.x, y + p.y);
  87. }
  88.  
  89. Point operator-(const Point & p) const // вычитание 2х векторов
  90. {
  91. return Point(x - p.x, y - p.y);
  92. }
  93.  
  94. Point operator-() const // обратный вектор
  95. {
  96. return Point(-x, -y);
  97. }
  98.  
  99. Point operator*(double k) const // умножение вектора на скаляр
  100. {
  101. return Point(x * k, y * k);
  102. }
  103.  
  104. Point operator/(double k) const // деление вектора на скаляр
  105. {
  106. return Point(x / k, y / k);
  107. }
  108.  
  109. double operator%(const Point & p) const // скалярное произведение
  110. {
  111. return x * p.x + y * p.y;
  112. }
  113.  
  114. double operator*(const Point & p) const // векторное произведение
  115. {
  116. return x * p.y - y * p.x;
  117. }
  118.  
  119. double length() const // длина вектора по определению из ан.гема (корень из скалярного квадрата)
  120. {
  121. return mySqrt(*this % *this);
  122. }
  123.  
  124. double distTo(const Point & p) const //расстояние между 2мя точками - модуль вектора между ними
  125. {
  126. return (*this - p).length();
  127. }
  128.  
  129. double distTo(const Point & A, const Point & B) const // расстояние от точки до прямой (всегда >= 0)
  130. {
  131. double d = A.distTo(B);
  132. if(doubleEqual(d, 0) ) // прямая должна задаваться двумя! точками
  133. {
  134. throw "A = B";
  135. }
  136. double s = (*this - A) * (*this - B); // удвоенная площадь треугольника
  137. return fabs(s) / d; // метод площадей
  138. }
  139.  
  140. Point normalize(double k = 1) const // выставляет длину вектора в k
  141. {
  142. double len = length(); // Текущая длина
  143. if(doubleEqual(len, 0) ) // если длина ноль
  144. {
  145. if(doubleEqual(k, 0) )
  146. {
  147. return Point();
  148. }
  149. throw "zero-size vector"; //кроме нулевой никакую получить не можем
  150. }
  151. return *this * (k / len);
  152. }
  153.  
  154. Point getH(const Point & A, const Point & B) const // опускаем высоту из точки на прямую (A, B)
  155. {
  156. Point C = *this;
  157. Point v = B - A; // направляющий вектор прямой
  158. Point u = C - A; // вектор, проекция которого нам нужна
  159. double k = v % u / v.length(); // нашли длину проекции
  160. v = v.normalize(k); // нашли проекцию u на v
  161. Point H = A + v; // подвинули точку A в проекцию конца вектора u, отложенного из A
  162. return H;
  163. }
  164.  
  165. Point rotate() const // поворот на 90 градусов против часовой стрелки (положительное направление)
  166. {
  167. return Point(-y, x);
  168. }
  169.  
  170. Point rotate(double alpha) const // поворот на угол alpha против часовой стрелки
  171. // (по часовой стрелке, если alpha < 0)
  172. {
  173. return rotate(cos(alpha), sin(alpha) ); // делегируем задачу другому экземпляру функции
  174. }
  175.  
  176. Point rotate(double cosa, double sina) const // поворот с заданными косинусом и синусом
  177. {
  178. Point v = *this;
  179. Point u = v.rotate(); // вектор, перпендикулярный v, теперь (v, u) - базис, в котором мы знаем ответ
  180. Point w = v * cosa + u * sina; // зная координаты в базисе (v, u), нашли w
  181. return w;
  182. }
  183.  
  184. bool isZero() const // проверка на то, что точка нулевая без сложных операций и погрешности
  185. {
  186. return doubleEqual(x, 0) && doubleEqual(y, 0);
  187. }
  188.  
  189. bool isOnLine(const Point & A, const Point & B) const // точка на прямой?
  190. {
  191. return doubleEqual( (A - *this) * (B - *this), 0);
  192. }
  193.  
  194. bool isInSegment(const Point & A, const Point & B) const // точка внутри отрезка?
  195. {
  196. return isOnLine(A, B) && doubleLessOrEqual( (A - *this) % (B - *this), 0 );
  197. }
  198.  
  199. bool isInSegmentStrictly(const Point & A, const Point & B) const // точка внутри отрезка строго?
  200. {
  201. return isOnLine(A, B) && doubleLess( (A - *this) % (B - *this), 0 );
  202. }
  203.  
  204. double getAngle() const
  205. {
  206. return atan2(y, x); // угол между вектором и осью ОХ
  207. }
  208.  
  209. double getAngle(Point u) const
  210. {
  211. Point v = *this;
  212. return atan2(v * u, v % u); // ориентированный угол между векторами
  213. }
  214.  
  215. };
  216.  
  217.  
  218. int getIntersection // ищем пересечение прямой (A, B) и прямой (C, D)
  219. (
  220. const Point & A,
  221. const Point & B,
  222. const Point & C,
  223. const Point & D,
  224. Point & O
  225. )
  226. {
  227. Point v = B - A; // направляющий вектор прямой (A, B)
  228. double s1 = (C - A) * (D - A); // площадь треугольника A, C, D
  229. double s2 = (D - B) * (C - B); // площадь треугольника B, D, C
  230. double s = s1 + s2; // площадь четурёхугольника
  231. if(doubleEqual(s, 0) ) // прямые параллельны (или совпадают)
  232. {
  233. if(!A.isOnLine(C, D) ) // прямые параллельны
  234. {
  235. return 0; // пересечение пусто
  236. }
  237. return 2; // больше 1ой точки в пересечении
  238. }
  239. v = v / s;
  240. v = v * s1; // вектора AO и AB пропорциональны площадям s1 и s
  241. O = A + v; // нашли точку пересечения
  242. return 1; // 1 точка в пересечении
  243. }
  244.  
  245.  
  246. int getIntersection // ищем пересечение 2х окружностей с центрами в A, B, радиусами rA, rB
  247. (
  248. const Point & A,
  249. double rA,
  250. const Point & B,
  251. double rB,
  252. Point & M,
  253. Point & N
  254. )
  255. {
  256. double d = A.distTo(B); // расстояние между точками
  257. if(doubleLess(rA + rB, d) || doubleLess(d, fabs(rA - rB)) ) // если окружности не касаются, то точек 0
  258. {
  259. return 0;
  260. }
  261. double a = (sqr(rA) - sqr(rB) + sqr(d) ) / 2 / d; // длину проекции отрезка (от A до пересечения окружностей) на прямую AB
  262. double h = mySqrt(sqr(rA) - sqr(a)); //расстояние о точки пересечения окружностей до прямой AB
  263. Point v = B - A; //направляющий вектор прямой AB
  264. Point u = v.rotate(); // нормальный вектор к прямой AB
  265. v = v.normalize(a);
  266. u = u.normalize(h); //нормируем до нужных длин оба вектора
  267. Point H = A + v;
  268. M = H + u;
  269. N = H - u;
  270. if(u.isZero() ) return 1; //если u = 0, то окружности касаются
  271. return 2;
  272. }
  273.  
  274.  
  275.  
  276. int getIntersection // ищем пересечение прямой (A, B) и окружности (O, r)
  277. (
  278. const Point & A,
  279. const Point & B,
  280. const Point & O,
  281. double r,
  282. Point & M,
  283. Point & N
  284. )
  285. {
  286. double h = O.distTo(A, B);
  287. if(doubleLess(r, h) ) //если окружность далеко от прямой
  288. {
  289. return 0;
  290. }
  291. Point H = O.getH(A, B); //уронили высоту на AB
  292. Point v = B - A; //взяли направляющий вектор прямой
  293. double k = mySqrt(sqr(r) - sqr(h) ); // величина, на которую надо подвинуть H до точки пересечения окружности и прямой
  294. v = v.normalize(k);
  295. M = H + v;
  296. N = H - v;
  297. if(v.isZero() ) return 1;
  298. return 2;
  299. }
  300.  
  301.  
  302. int getTangent // получаем касательные из точки A к оркужности (O, r)
  303. (
  304. const Point & A,
  305. const Point & O,
  306. double r,
  307. Point & M,
  308. Point & N
  309. )
  310. {
  311. Point v = O - A;
  312. double d = v.length();
  313. if(doubleLess(d, r) ) return 0; // точка внутри, не существует касательной
  314. double alpha = asin(r / d); // нашли угол между касательной и вектором v
  315. double L = mySqrt(sqr(d) - sqr(r)); // длина касательной
  316. v = v.normalize(L); // теперь v имеет длину касательной
  317. M = A + v.rotate(alpha);
  318. N = A - v.rotate(alpha); // повернули вектор v в обе стороны и нашли концы обоих касательных
  319. if(doubleEqual(r, d) ) return 1;
  320. return 2;
  321. }
  322.  
  323.  
  324. void getOutTangent // получаем внешние касательные к паре оркужностей
  325. (
  326. Point A,
  327. double rA,
  328. Point B,
  329. double rB,
  330. pair<Point, Point> & P,
  331. pair<Point, Point> & Q
  332. )
  333. {
  334. if(rA > rB)
  335. {
  336. swap(rA, rB);
  337. swap(A, B);
  338. }
  339. //Point u = (A - B).rotate(asin(r / d)).rotate().normalize(rA);
  340. //P.first = A + u;
  341. //Q.first = A - u;
  342. Point T1, T2;
  343. //getTangent(A, B, rB - rA, T1, T2); //сжали окружности на rA , получили ответ для неё, потом раздвинули прямые на rA в стороны
  344. //P.second = T1 + u;
  345. //Q.second = T2 - u;
  346. }
  347.  
  348. signed main() {
  349. ios_base::sync_with_stdio(false);
  350. cin.tie(0);
  351. cout.tie(0);
  352.  
  353. double r,x1,y1,x2,y2;
  354. cin >> r >> x1 >> y1 >> x2 >> y2;
  355. double len=sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
  356. if(len>r){
  357. cout << x1 <<" " << y1 << endl;
  358. }
  359. double cenx=(x1+x2)/2;
  360. double ceny=(y1+y2)/2;
  361. len=sqrt((x1-cenx)*(x1-cenx)+(y1-ceny)*(y1-ceny));
  362. cout << cenx << " " << ceny << " " << len;
  363. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement