Advertisement
MiinaMagdy

10250 - The Other Two Trees

Oct 18th, 2023
722
1
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 5.31 KB | None | 1 0
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/tree_policy.hpp>
  4.  
  5. using namespace std;
  6. using namespace __gnu_pbds;
  7. #define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
  8. #define multi_ordered_set tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update>
  9. #define endl "\n"
  10. #define MOD 1000000007
  11. #define INF 2000000000
  12. #define all(s) s.begin(), s.end()
  13. #define rall(s) s.rbegin(), s.rend()
  14. #define sz(x) int(x.size())
  15. #define crossProd(A,B) ((conj(A)*(B)).imag())
  16. #define dotProd(A,B) ((conj(A)*(B)).real())
  17.  
  18. typedef long long ll;
  19. typedef long double ld;
  20. typedef unsigned long long ull;
  21.  
  22. #define EPS 1e-9
  23. #define PI acos(-1)
  24. #define X real()
  25. #define Y imag()
  26. #define normalize(a) (a) / length(a)
  27. #define lengthSqr(p) dot_prod(p, p)
  28. // #define rotateO(p, ang) p * exp(point(0, ang))
  29. // #define rotateA(p, about, ang) rotateO(vector((about), (p)), ang) + (about)
  30. #define reflicatO(v, m) conj(v / m) * m
  31. #define reflicatA(v, about, m) conj(vector(about, v) / vector(about, m)) * vector(about, m) + about
  32.  
  33. template<typename T>
  34. class point {
  35. public:
  36.     T x, y;
  37.     point() {
  38.         x = y = 0;
  39.     }
  40.     point(T _x, T _y) {
  41.         x = _x;
  42.         y = _y;
  43.     }
  44.     point(const point<T> &p) {
  45.         x = p.x;
  46.         y = p.y;
  47.     }
  48.     // vector from point a to point b
  49.     point(const point<T> &a, const point<T> &b) {
  50.         *this = b - a;
  51.     }
  52.     point operator=(const point<T> &p) {
  53.         x = p.x;
  54.         y = p.y;
  55.         return *this;
  56.     }
  57.     point operator+(const point<T> &p) const {
  58.         return point(x + p.x, y + p.y);
  59.     }
  60.     point operator-(const point<T> &p) const {
  61.         return point(x - p.x, y - p.y);
  62.     }
  63.     // dot product
  64.     T operator*(const point<T> &p) const {
  65.         return x * p.x + y * p.y;
  66.     }
  67.     // cross product
  68.     T operator^(const point<T> &p) const {
  69.         return x * p.y - y * p.x;
  70.     }
  71.     point operator*(const T &factor) const {
  72.         return point(x * factor, y * factor);
  73.     }
  74.     point operator/(const T &factor) const {
  75.         return point(x / factor, y / factor);
  76.     }
  77.     friend istream &operator>>(istream &is, point<T> &p) {
  78.         is >> p.x >> p.y;
  79.         return is;
  80.     }
  81.     friend ostream &operator<<(ostream &os, const point<T> &p) {
  82.         os << p.x << " " << p.y;
  83.         return os;
  84.     }
  85.     bool operator==(const point<T> &p) const {
  86.         return (x == p.x && y == p.y);
  87.     }
  88.     bool operator!=(const point<T> &p) const {
  89.         return (x != p.x || y != p.y);
  90.     }
  91.     double arg() const {
  92.         return atan2l(y, x);
  93.     }
  94.     T lenSqr() const {
  95.         return x * x + y * y;
  96.     }
  97.     double len() const {
  98.         return hypot(x, y);
  99.     }
  100.     // distance
  101.     double dist(const point<T> &p) const {
  102.         return hypot(x - p.x, y - p.y);
  103.     }
  104.     // distance squared
  105.     T distSqr(const point<T> &p) const {
  106.         return (x - p.x) * (x - p.x) + (y - p.y) * (y - p.y);
  107.     }
  108.     // returns 1 for counterclockwise order
  109.     // returns -1 for clockwise order
  110.     // returns 0 if the points are collinear
  111.     int orientation(const point<T> &p, const point<T> &q) const {
  112.         T val = (q - p) ^ (*this - q);
  113.         if (val == 0)
  114.             return 0;
  115.         return (val > 0) ? 1 : -1;
  116.     }
  117.     // check intersection between line segment p1q1 and line segment p2q2
  118.     static bool intersect_ab_cd(point<T> a, point<T> b, point<T> c, point<T> d, point<T> &intersect) {
  119.         point<T> u(a, b);
  120.         point<T> v(c, d);
  121.         point<T> w(c, a);
  122.         T d1 = u ^ v;
  123.         T d2 = v ^ w;
  124.         T d3 = u ^ w;
  125.         if (d1 == 0)
  126.             return false;
  127.         double t1 = d2 / d1;
  128.         double t2 = d3 / d1;
  129.         intersect = a + u * t1;
  130.         return true; // e.g ab is a line, cd is a line
  131.         // return t1 >= EPS && t2 >= EPS && t2 <= 1 + EPS; // e.g ab is a ray, cd is a segment
  132.     }
  133.     // rotate point by angle theta in radians counter-clockwise around origin
  134.     point<T> rotateO(double theta) const {
  135.         return point<T>(x * cos(theta) - y * sin(theta), x * sin(theta) + y * cos(theta));
  136.     }
  137.     void desmosDisplay() {
  138.         cout << fixed << setprecision(9) << "(" << x << "," << y << ")" << endl;
  139.     }
  140.     point<T> midPoint(point<T> p) {
  141.         return point<T>((*this + p) / 2);
  142.     }
  143. };
  144.  
  145. // ab segment, c point
  146. double segPointDist(point<double> a, point<double> b, point<double> c, point<double> &ans) {
  147.     point<double> u(a, b), v(b, c), w(a, c);
  148.     double d1, d2;
  149.     if ((d1 = w * u) < -EPS) {
  150.         ans = a;
  151.         return a.dist(c);
  152.     }
  153.     if ((d2 = u * u) <= d1) {
  154.         ans = b;
  155.         return b.dist(c);
  156.     }
  157.     double t = d1 / d2;
  158.     ans = a + u * t;
  159.     return ans.dist(c);
  160. }
  161.  
  162. void solve() {
  163.     cout << fixed << setprecision(10);
  164.     point<ld> p1, p2;
  165.     while (cin >> p1 >> p2) {
  166.         point<ld> mp = p1.midPoint(p2);
  167.         p1 = p1 - mp;
  168.         p2 = p2 - mp;
  169.         p1 = point<ld>(-p1.y, p1.x);
  170.         p2 = point<ld>(-p2.y, p2.x);
  171.         cout << p1 + mp << " " << p2 + mp << endl;
  172.     }
  173. }
  174.  
  175. int main(void)
  176. {
  177.     ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
  178.     int testcase = 1;
  179.     // cin >> testcase;
  180.     while (testcase--)
  181.         solve();
  182.     return 0;
  183. }
Tags: UVA geometry
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement