SHARE
TWEET

Untitled

a guest Nov 11th, 2019 71 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <iomanip>
  3. #include <cmath>
  4. #include <vector>
  5. #include <list>
  6. #include <stdio.h>
  7. #include <algorithm>
  8. #include <chrono>
  9. #include <iostream>
  10. #include <random>
  11. #include <set>
  12. #include <vector>
  13. #include <thread_db.h>
  14.  
  15. namespace Geom {
  16.     template<class T>
  17.     class Vector {
  18.      public:
  19.         T x;
  20.         T y;
  21.  
  22.         Vector(T x, T y) {
  23.             this->x = x;
  24.             this->y = y;
  25.         };
  26.  
  27.         explicit Vector() {
  28.             Vector(0, 0);
  29.         };
  30.  
  31.         T norm() {
  32.             return std::sqrt(this->x * this->x + this->y * this->y);
  33.         };
  34.     };
  35.  
  36.     template<class T>
  37.     Vector<T> operator+(const Vector<T> &first, const Vector<T> &second) {
  38.         return Vector<T>(first.x + second.x, first.y + second.y);
  39.     };
  40.  
  41.     template<class T>
  42.     Vector<T> operator-(const Vector<T> &first, const Vector<T> &second) {
  43.         return Vector<T>(first.x - second.x, first.y - second.y);
  44.     };
  45.  
  46.     template<class T>
  47.     T operator*(Vector<T> &first, const Vector<T> &second) {
  48.         return first.x * second.x + first.y * second.y;
  49.     };
  50.  
  51.     template<class T, class U>
  52.     Vector<T> operator*(U factor, const Vector<T> &first) {
  53.         return Vector<T>(factor * first.x, factor * first.y);
  54.     };
  55.  
  56.     template<class T, class U>
  57.     Vector<T> operator*(const Vector<T> &first, U factor) {
  58.         return factor * first;
  59.     };
  60.  
  61.     template<class T, class U>
  62.     Vector<T> operator/(const Vector<T> &first, U delim) {
  63.         return Vector<T>(first.x / delim, first.y / delim);
  64.     };
  65.  
  66.     template<class T>
  67.     bool operator==(const Vector<T> &first, const Vector<T> &second) {
  68.         return (first.x == second.x) & (first.y == second.y);
  69.     };
  70.  
  71.     template<class T>
  72.     bool operator!=(const Vector<T> &first, Vector<T> &second) {
  73.         return !(first == second);
  74.     };
  75.  
  76.     template<class T>
  77.     bool operator>(const Vector<T> &first, const Vector<T> &second) {
  78.         return (first.x > second.x) || (first.x == second.x && first.y > second.y);
  79.     };
  80.  
  81.     template<class T>
  82.     T vector_prod_norm(const Vector<T> first, const Vector<T> second) {
  83.         return first.x * second.y - second.x * first.y;
  84.     };
  85.  
  86.     class Segment {
  87.      public:
  88.         Vector<long long> start, end;
  89.         Segment(Vector<long long> start, Vector<long long> end) {
  90.             if (start > end) {
  91.                 std::swap(start, end);
  92.             }
  93.  
  94.             this->start = start;
  95.             this->end = end;
  96.         }
  97.  
  98.         bool is_vertical() {
  99.             return start.x == end.x;
  100.         }
  101.  
  102.         bool Contains(Vector<long long> point) {
  103.             return this->start.x <= point.x && point.x <= this->end.x
  104.                 && this->start.y <= point.y && point.y <= this->end.y
  105.                 && vector_prod_norm(point - this->start, this->end - this->start) == 0;
  106.         }
  107.     };
  108.  
  109.     bool higher_at_point(const Segment &a, const Segment &b, long long point) {
  110.         long long a_num = (point - a.start.x) * a.end.y - (point - a.end.x) * a.start.y;
  111.         long long a_den = a.end.x - a.start.x;
  112.         if (a_den == 0) {
  113.             a_num = a.start.y;
  114.             a_den = 1;
  115.         }
  116.  
  117.         long long b_num = (point - b.start.x) * b.end.y - (point - b.end.x) * b.start.y;
  118.         long long b_den = b.end.x - b.start.x;
  119.         if (b_den == 0) {
  120.             b_num = b.start.y;
  121.             b_den = 1;
  122.         }
  123.  
  124.         return a_num * b_den > b_num * a_den;
  125.     }
  126.  
  127.     bool operator>(const Segment &a, const Segment &b) {
  128.         if (a.start == b.end) {
  129.             return true;
  130.         } else if (b.start == a.end) {
  131.             return false;
  132.         } else if (a.start == b.start) {
  133.             return vector_prod_norm(a.end - a.start, b.end - b.start) < 0;
  134.         } else {
  135.             long long check_point = a.start.x > b.start.x ? a.start.x : b.start.x;
  136.             return higher_at_point(a, b, check_point);
  137.         }
  138.     }
  139.  
  140.     bool operator<(const Segment &a, const Segment &b) {
  141.         return b > a;
  142.     }
  143.  
  144.     bool operator==(const Segment a, const Segment b) {
  145.         return a.start == b.start && a.end == b.end;
  146.     }
  147.  
  148.     bool operator!=(const Segment a, const Segment b) {
  149.         return !(a == b);
  150.     }
  151. };
  152.  
  153. namespace Treap {
  154.     template<class T>
  155.     struct TreapNode {
  156.       T key;
  157.       long long prior;
  158.       long long cnt;
  159.       TreapNode *left_n;
  160.       TreapNode *right_n;
  161.  
  162.       TreapNode(T key, long long prior)
  163.           : key(key),
  164.             prior(prior),
  165.             cnt(0),
  166.             left_n(nullptr),
  167.             right_n(nullptr) {};
  168.     };
  169.  
  170.     template<class T>
  171.     class Treap {
  172.      public:
  173.         Treap(std::mt19937 rng)
  174.             : head_(nullptr),
  175.               rng_(rng) {};
  176.  
  177.         void Insert(T new_key) {
  178.             auto new_node = GetNewNode_(new_key);
  179.             Insert_(head_, new_node);
  180.             check(head_, nullptr, nullptr);
  181.         }
  182.  
  183.         void Delete(T key) {
  184.             Delete_(head_, key);
  185.             check(head_, nullptr, nullptr);
  186.         }
  187.  
  188.         long long GetOrderStat(T key) {
  189.             return GetOrderStat_(head_, key);
  190.         }
  191.  
  192.         bool check(TreapNode<T> *&node, T *upper, T *lower) {
  193.             if (!node) return false;
  194.             if (node->left_n) {
  195.                 if (node->left_n->key > node->key || (lower && *lower > node->left_n->key)) throw std::runtime_error("DD");
  196.                 check(node->left_n, &node->key, lower);
  197.             }
  198.             if (node->right_n) {
  199.                 if (node->right_n->key < node->key || (upper && *upper < node->right_n->key)) throw std::runtime_error("FF");
  200.                 check(node->right_n, upper, &node->key);
  201.             }
  202.         }
  203.  
  204.         TreapNode<T> *head_;
  205.      protected:
  206.         std::mt19937 rng_;
  207.  
  208.         TreapNode<T> *GetNewNode_(T key) {
  209.             long long prior = rng_();
  210.             return new TreapNode<T>(key, prior);
  211.         }
  212.  
  213.         long long GetOrderStat_(TreapNode<T> *&node, T key) {
  214.             if (node->key == key) {
  215.                 return GetCount_(node->left_n);
  216.             } else if (node->key > key) {
  217.                 return GetOrderStat_(node->left_n, key);
  218.             } else {
  219.                 return 1 + GetCount_(node->left_n) + GetOrderStat_(node->right_n, key);
  220.             }
  221.         }
  222.  
  223.         void Insert_(TreapNode<T> *&source, TreapNode<T> *&new_node) {
  224.             if (!source) {
  225.                 source = new_node;
  226.             } else if (new_node->prior < source->prior) {
  227.                 Split_(source, new_node->key, new_node->left_n, new_node->right_n);
  228.                 source = new_node;
  229.             } else {
  230.                 if (source->key > new_node->key) {
  231.                     Insert_(source->left_n, new_node);
  232.                 } else {
  233.                     Insert_(source->right_n, new_node);
  234.                 }
  235.             }
  236.             UpdateCount_(source);
  237.         }
  238.  
  239.         void Delete_(TreapNode<T> *&current_node, T key) {
  240.             if (!current_node) throw std::runtime_error("NO SUCH ELEMENT");
  241.  
  242.             if (current_node->key == key) {
  243.                 Merge_(current_node, current_node->left_n, current_node->right_n);
  244.             } else if (current_node->key > key) {
  245.                 Delete_(current_node->left_n, key);
  246.             } else {
  247.                 Delete_(current_node->right_n, key);
  248.             }
  249.             UpdateCount_(current_node);
  250.         }
  251.  
  252.         void Merge_(TreapNode<T> *&destination, TreapNode<T> *&left_sub, TreapNode<T> *&right_sub) {
  253.             if (!left_sub) {
  254.                 destination = right_sub;
  255.             } else if (!right_sub) {
  256.                 destination = left_sub;
  257.             } else if (left_sub->prior < right_sub->prior) {
  258.                 Merge_(left_sub->right_n, left_sub->right_n, right_sub);
  259.                 destination = left_sub;
  260.             } else {
  261.                 Merge_(right_sub->left_n, left_sub, right_sub->left_n);
  262.                 destination = right_sub;
  263.             }
  264.             UpdateCount_(destination);
  265.         }
  266.  
  267.         void Split_(TreapNode<T> *&source, T key, TreapNode<T> *&left_sub, TreapNode<T> *&right_sub) {
  268.             if (!source) {
  269.                 left_sub = right_sub = nullptr;
  270.             } else if (source->key > key) {
  271.                 right_sub = source;
  272.                 Split_(source->left_n, key, left_sub, source->left_n);
  273.             } else {
  274.                 left_sub = source;
  275.                 Split_(source->right_n, key, source->right_n, right_sub);
  276.             }
  277.             UpdateCount_(left_sub);
  278.             UpdateCount_(right_sub);
  279.         }
  280.  
  281.         long long GetCount_(TreapNode<T> *&node) {
  282.             if (!node) {
  283.                 return 0;
  284.             }
  285.             return node->cnt;
  286.         }
  287.  
  288.         virtual void UpdateCount_(TreapNode<T> *&node) {
  289.             if (!node) {
  290.                 return;
  291.             }
  292.             auto left_cnt = GetCount_(node->left_n);
  293.             auto right_cnt = GetCount_(node->right_n);
  294.             node->cnt = 1 + left_cnt + right_cnt;
  295.         }
  296.     };
  297.  
  298.     class SegmentTreap : public Treap<Geom::Segment> {
  299.      public:
  300.         explicit SegmentTreap(std::mt19937 rng)
  301.             : Treap<Geom::Segment>(rng) {};
  302.         bool HasSegmentWithPoint(Geom::Vector<long long> point) {
  303.             return HasSegmentWithPoint_(head_, Geom::Segment(point, point));
  304.         }
  305.  
  306.      private:
  307.         bool HasSegmentWithPoint_(TreapNode<Geom::Segment> *&curr_node, Geom::Segment point) {
  308.             if (!curr_node) {
  309.                 return false;
  310.             } else if (curr_node->key.Contains(point.start)) {
  311.                 return true;
  312.             } else if (curr_node->key > point) {
  313.                 return HasSegmentWithPoint_(curr_node->left_n, point);
  314.             } else {
  315.                 return HasSegmentWithPoint_(curr_node->right_n, point);
  316.             }
  317.         }
  318.  
  319.         void UpdateCount_(TreapNode<Geom::Segment> *&node) override {
  320.             if (!node) {
  321.                 return;
  322.             }
  323.             auto left_cnt = GetCount_(node->left_n);
  324.             auto right_cnt = GetCount_(node->right_n);
  325.             if (node->key.is_vertical()) {
  326.                 node->cnt = left_cnt + right_cnt;
  327.             } else {
  328.                 node->cnt = 1 + left_cnt + right_cnt;
  329.             }
  330.         }
  331.     };
  332. }
  333.  
  334. namespace Solver {
  335.     class Solver {
  336.      public:
  337.         enum PointResult {
  338.           Inside,
  339.           Border,
  340.           Outside
  341.         };
  342.  
  343.         Solver &read_input() {
  344.             std::cin >> n;
  345.             Geom::Vector<long long> first_point;
  346.             Geom::Vector<long long> prev_point;
  347.             Geom::Vector<long long> curr_point;
  348.  
  349.             for (int i = 0; i < n; ++i) {
  350.                 long long x, y;
  351.                 std::cin >> x >> y;
  352.                 curr_point = Geom::Vector<long long>(x, y);
  353.                 if (i == 0) {
  354.                     first_point = curr_point;
  355.                 } else if (curr_point != prev_point) {
  356.                     RegisterSegment(prev_point, curr_point);
  357.                 }
  358.                 prev_point = curr_point;
  359.             }
  360.             if (curr_point != first_point) {
  361.                 RegisterSegment(curr_point, first_point);
  362.             }
  363.  
  364.             std::cin >> k;
  365.             results.resize(k);
  366.  
  367.             for (int i = 0; i < k; ++i) {
  368.                 long long x, y;
  369.                 std::cin >> x >> y;
  370.                 auto point = Geom::Vector<long long>(x, y);
  371.                 RegisterPoint(point, i);
  372.             }
  373.  
  374.             return *this;
  375.         };
  376.  
  377.         Solver &solve() {
  378.             std::sort(events.begin(), events.end());
  379.  
  380.             std::mt19937 rng(0);
  381.             Treap::SegmentTreap activeSegments(rng);
  382.  
  383.             for (auto event : events) {
  384.                 switch (event.type) {
  385.                     case SegmentStart:activeSegments.Insert(event.segment);
  386.                         break;
  387.                     case SegmentEnd:activeSegments.Delete(event.segment);
  388.                         break;
  389.                     case TaskPointBorder:
  390.                     case TaskPointInsideOutside:FindTaskPointAnswer(activeSegments, event);
  391.                         break;
  392.                 }
  393.             }
  394.             return *this;
  395.         }
  396.  
  397.         Solver &PrintSolution() {
  398.             for (auto &result : results) {
  399.                 switch (result) {
  400.                     case Outside:std::cout << "OUTSIDE\n";
  401.                         break;
  402.                     case Inside:std::cout << "INSIDE\n";
  403.                         break;
  404.                     case Border:std::cout << "BORDER\n";
  405.                         break;
  406.                 }
  407.             }
  408.             return *this;
  409.         }
  410.  
  411.      private:
  412.         long long n, k;
  413.         std::vector<PointResult> results;
  414.         std::vector<Geom::Segment> vertical_segments;
  415.  
  416.         enum EventType : short {
  417.           SegmentStart,
  418.           TaskPointBorder,
  419.           SegmentEnd,
  420.           TaskPointInsideOutside,
  421.         };
  422.  
  423.         struct ScanLineEvent {
  424.           Geom::Segment segment;
  425.           Geom::Vector<long long> point;
  426.           EventType type;
  427.           long long task_point_index;
  428.  
  429.           ScanLineEvent(Geom::Segment segment,
  430.                         Geom::Vector<long long> point,
  431.                         EventType type,
  432.                         long long task_point_index = -1)
  433.               : segment(segment),
  434.                 point(point),
  435.                 type(type),
  436.                 task_point_index(task_point_index) {};
  437.  
  438.           bool operator<(ScanLineEvent &b) {
  439.               return (this->point.x < b.point.x) || (this->point.x == b.point.x && this->type < b.type);
  440.           }
  441.         };
  442.         std::vector<ScanLineEvent> events;
  443.  
  444.         void RegisterSegment(Geom::Vector<long long> point1, Geom::Vector<long long> point2) {
  445.             auto segment = Geom::Segment(point1, point2);
  446.             events.emplace_back(segment, segment.start, SegmentStart);
  447.             events.emplace_back(segment, segment.end, SegmentEnd);
  448.  
  449.             if (segment.is_vertical()) {
  450.                 vertical_segments.push_back(segment);
  451.             }
  452.         }
  453.  
  454.         void RegisterPoint(Geom::Vector<long long> point, long long task_point_index) {
  455.             auto segment = Geom::Segment(point, point);
  456.             events.emplace_back(segment, segment.start, TaskPointBorder, task_point_index);
  457.             events.emplace_back(segment, segment.start, TaskPointInsideOutside, task_point_index);
  458.         }
  459.  
  460.         void FindTaskPointAnswer(Treap::SegmentTreap active_segments, ScanLineEvent event) {
  461.             if (event.type != TaskPointBorder && event.type != TaskPointInsideOutside) {
  462.                 throw std::runtime_error("Invalid scanline event");
  463.             }
  464.  
  465.             if (event.type == TaskPointBorder) {
  466.                 if (active_segments.HasSegmentWithPoint(event.point)) {
  467.                     results[event.task_point_index] = Border;
  468.                 }
  469.             } else {
  470.                 if (results[event.task_point_index] == Border) {
  471.                     return;
  472.                 }
  473.                 active_segments.Insert(event.segment);
  474.                 auto num_segments_lower = active_segments.GetOrderStat(event.segment);
  475.                 if (num_segments_lower % 2 == 0) {
  476.                     results[event.task_point_index] = Outside;
  477.                 } else {
  478.                     results[event.task_point_index] = Inside;
  479.                 }
  480.                 active_segments.Delete(event.segment);
  481.             }
  482.         }
  483.     };
  484. }
  485.  
  486. int main() {
  487.     freopen("../aaaa.txt", "r", stdin);
  488.     long long n;
  489.     std::cin >> n;
  490.     for (int i = 0; i < n; ++i) {
  491.         Solver::Solver s;
  492.         s.read_input();
  493.         s.solve();
  494.         s.PrintSolution();
  495.         std::cout << "\n";
  496.     }
  497.  
  498.  
  499. //    std::set<long long> s;
  500. //    std::mt19937 rng(0);
  501. //    Treap::Treap<long long> t(rng);
  502. //
  503. //    for (int i = 0; i < 10000; ++i) {
  504. ////        auto x = Geom::Segment(Geom::Vector<long long>(0, i * 10 + rand() % 10),
  505. ////                               Geom::Vector<long long>(10, i * 10 + rand() % 10));
  506. //        t.Insert(i);
  507. //        t.check(t.head_, 100000000, -1000);
  508. ////        s.insert(i);
  509. //    }
  510. //
  511. //    for (auto x : s) {
  512. //        t.Delete(x);
  513. //        t.check(t.head_, 100000000, -1000);
  514. //    }
  515.  
  516.     return 0;
  517. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top