Advertisement
Guest User

Untitled

a guest
Dec 19th, 2018
93
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 7.58 KB | None | 0 0
  1. #include <iostream>
  2. #include <string>
  3. #include <vector>
  4. #include <set>
  5. #include <map>
  6. #include <algorithm>
  7.  
  8. class Point {
  9. public:
  10.     double x;
  11.     double y;
  12.  
  13.     Point() = default;
  14.  
  15.     Point(double x, double y) : x(x) , y(y)
  16.     {}
  17. };
  18.  
  19. double cr_prod(const Point& a, const Point& b) {
  20.     return a.x * b.y - b.x * a.y;
  21. }
  22.  
  23. enum PointPos {
  24.     OUTSIDE,
  25.     INSIDE,
  26.     BORDER
  27. };
  28.  
  29. enum SegmentPos {
  30.     ABOVE,
  31.     BELOW
  32. };
  33.  
  34. class Segment {
  35. private:
  36.     Point begin_;
  37.     Point end_;
  38.     SegmentPos pos_;
  39.  
  40. public:
  41.     Segment() = default;
  42.  
  43.     Segment(Point begin, Point end, SegmentPos pos) : begin_(begin), end_(end), pos_(pos)
  44.     {}
  45.  
  46.     Segment(Point pt) : Segment(pt, pt, ABOVE)
  47.     {}
  48.  
  49.     const Point& begin() const { return begin_; }
  50.  
  51.     const Point& end() const { return end_; }
  52.  
  53.     SegmentPos pos() const { return pos_; }
  54.  
  55.     bool is_vertical() const {
  56.         if (begin_.x == end_.x) return true;
  57.         return false;
  58.     }
  59.  
  60.     double get_y(double x) const {
  61.         if (is_vertical()) return begin_.y;
  62.         return begin_.y + (x - begin_.x) * (end_.y - begin_.y) / (end_.x - begin_.x);
  63.     }  
  64. };
  65.  
  66. enum EventOrder {
  67.     OPEN,
  68.     CLOSE,
  69.     QUERY
  70. };
  71.  
  72. struct Event {
  73.  
  74.     double loc;
  75.     EventOrder type;
  76.     size_t id;
  77.  
  78.     Event(double loc, EventOrder type, size_t id) : loc(loc), type(type), id(id)
  79.     {}
  80.  
  81.     Event(double loc, EventOrder type) : Event(loc, type, SIZE_MAX)
  82.     {}
  83. };
  84.  
  85.  
  86. struct CompOpenQueryClose {
  87.     bool operator() (const Event& a, const Event& b) const{
  88.         if (a.loc != b.loc) {
  89.             return a.loc < b.loc;
  90.         }
  91.         static std::vector<EventOrder> order = { EventOrder::OPEN, EventOrder::QUERY, EventOrder::CLOSE };
  92.         return std::find(order.begin(), order.end(), a.type) <
  93.             std::find(order.begin(), order.end(), b.type);
  94.     }
  95. };
  96.  
  97. struct CompCloseOpenQuery {
  98.     bool operator ()(const Event& a, const Event& b) const{
  99.         if (a.loc != b.loc) {
  100.             return a.loc < b.loc;
  101.         }
  102.         static std::vector<EventOrder> order = { EventOrder::CLOSE, EventOrder::OPEN, EventOrder::QUERY };
  103.         return std::find(order.begin(), order.end(), a.type) < std::find(order.begin(), order.end(), b.type);
  104.     }
  105. };
  106.  
  107. struct CompPoint {
  108.     bool operator ()(const Point& a, const Point& b) const{
  109.         if (std::make_pair(a.x, a.y) < std::make_pair(b.x, b.y)) return true;
  110.         return false;
  111.     }
  112. };
  113.  
  114. struct CompSeg {
  115.     bool operator ()(const Segment& a, const Segment& b) const{
  116.         double intersec_begin = std::max(a.begin().x, b.begin().x);
  117.         double intersec_end = std::min(a.end().x, b.end().x);
  118.         std::pair< double, double > ord_a = std::make_pair(a.get_y(intersec_begin), a.get_y(intersec_end));
  119.         std::pair< double, double > ord_b = std::make_pair(b.get_y(intersec_begin), b.get_y(intersec_end));
  120.         return ord_a < ord_b;
  121.     }
  122. };
  123.  
  124. struct Data {
  125.     std::vector<Point> queries;
  126.     std::vector <Point> vertices;
  127. };
  128.  
  129. class BelongPoints {
  130. public:
  131.  
  132.  
  133.     void init(const Data& data) {
  134.         ver_ = data.vertices;
  135.         qr_ = data.queries;
  136.     }
  137.  
  138.     std::vector<PointPos> MakeAns() {
  139.         ans_.assign(qr_.size(), PointPos::OUTSIDE);
  140.         MakeSeg();
  141.  
  142.         OnVertex();
  143.         VerticalSegments();
  144.  
  145.         std::vector<Event> events;
  146.         for (size_t i = 0; i < seg_.size(); ++i) {
  147.             if (!seg_[i].is_vertical()) {
  148.                 events.emplace_back(seg_[i].begin().x, EventOrder::OPEN, i);
  149.                 events.emplace_back(seg_[i].end().x, EventOrder::CLOSE, i);
  150.             }
  151.         }
  152.  
  153.         for (size_t i = 0; i < qr_.size(); ++i) {
  154.             events.emplace_back(qr_[i].x, EventOrder::QUERY, i);
  155.         }
  156.  
  157.         sort(events.begin(), events.end(), CompCloseOpenQuery());
  158.         std::multiset<Segment, CompSeg> opened_edges;
  159.  
  160.         for (const Event& event : events) {
  161.             switch (event.type) {
  162.             case EventOrder::OPEN:
  163.                 opened_edges.insert(seg_[event.id]);
  164.                 break;
  165.             case EventOrder::CLOSE:
  166.                 opened_edges.erase(opened_edges.find(seg_[event.id]));
  167.                 break;
  168.             case EventOrder::QUERY:
  169.                 Segment query(qr_[event.id]);
  170.                 auto it = opened_edges.lower_bound(query);
  171.                 if (it != opened_edges.end() && it->get_y(qr_[event.id].x) == qr_[event.id].y) {
  172.                     UpdateAnswer(event.id, BORDER);
  173.                 }
  174.                 if (it != opened_edges.begin()) {
  175.                     --it;
  176.                     if (it->pos() == ABOVE) {
  177.                         UpdateAnswer(event.id, INSIDE);
  178.                     }
  179.                 }
  180.             }
  181.         }
  182.         return ans_;
  183.     }
  184.  
  185.  
  186. private:
  187.     std::vector<Point> qr_, ver_;
  188.     std::vector<Segment> seg_;
  189.     std::vector<PointPos> ans_;
  190.  
  191.     void UpdateAnswer(size_t id, PointPos pos) {
  192.         ans_[id] = std::max(ans_[id], pos);
  193.     }
  194.  
  195.     bool SignOrientedArea() const {
  196.         double s = 0;
  197.         for (size_t i = 0; i < ver_.size(); ++i) {
  198.             s += cr_prod(ver_[i], ver_[(i + 1) % ver_.size()]);
  199.         }
  200.         return s >= 0;
  201.     }
  202.  
  203.     void MakeSeg() {
  204.         seg_.resize(ver_.size());
  205.         for (size_t i = 0; i < ver_.size(); ++i) {
  206.             Point begin = ver_[i];
  207.             Point end = ver_[(i + 1) % ver_.size()];
  208.             bool cmp = CompPoint()(begin, end);
  209.             SegmentPos pos = cmp ^ (!SignOrientedArea()) ? ABOVE : BELOW;
  210.             if (!cmp) {
  211.                 std::swap(begin, end);
  212.             }
  213.             seg_[i] = Segment(begin, end, pos);
  214.         }
  215.     }
  216.  
  217.     void BelongVerticalSegment(const std::vector<Segment>& segments, const std::vector<size_t>& queries) {
  218.         std::vector<Event> events;
  219.         for (const Segment& seg : segments) {
  220.             events.emplace_back(std::min(seg.begin().y, seg.end().y), EventOrder::OPEN);
  221.             events.emplace_back(std::max(seg.begin().y, seg.end().y), EventOrder::CLOSE);
  222.         }
  223.         for (size_t id : queries) {
  224.             events.emplace_back(qr_[id].y, EventOrder::QUERY, id);
  225.         }
  226.         sort(events.begin(), events.end(), CompOpenQueryClose());
  227.         size_t cnt = 0;
  228.         for (const Event& event : events) {
  229.             switch (event.type) {
  230.             case EventOrder::OPEN:
  231.                 cnt++;
  232.                 break;
  233.             case EventOrder::CLOSE:
  234.                 cnt--;
  235.                 break;
  236.             case EventOrder::QUERY:
  237.                 if (cnt) UpdateAnswer(event.id, BORDER);
  238.             }
  239.         }
  240.     }
  241.  
  242.     void VerticalSegments() {
  243.         std::map<double, std::vector<Segment>> vertical;
  244.         for (const Segment& seg : seg_) {
  245.             if (seg.is_vertical()) {
  246.                 vertical[seg.begin().x].push_back(seg);
  247.             }
  248.         }
  249.  
  250.         std::map<double, std::vector<size_t>> queries;
  251.         for (size_t i = 0; i < qr_.size(); ++i) {
  252.             queries[qr_[i].x].push_back(i);
  253.         }
  254.  
  255.         for (auto& i : vertical) {
  256.             BelongVerticalSegment(i.second, queries[i.first]);
  257.         }
  258.     }
  259.  
  260.     void OnVertex() {
  261.         std::set<Point, CompPoint> ver(ver_.begin(), ver_.end());
  262.         for (size_t i = 0; i < qr_.size(); ++i) {
  263.             if (ver.count(qr_[i])) {
  264.                 UpdateAnswer(i, BORDER);
  265.             }
  266.         }
  267.     }
  268. };
  269.  
  270.  
  271. Data InputData(std::istream& in) {
  272.     Data data;
  273.     size_t cnt_vert;
  274.     size_t cnt_qr;
  275.     in >> cnt_vert;
  276.     data.vertices.resize(cnt_vert);
  277.     for (auto& vertex : data.vertices) {
  278.         in >> vertex.x >> vertex.y;
  279.     }
  280.     in >> cnt_qr;
  281.     data.queries.resize(cnt_qr);
  282.     for (auto& query : data.queries) {
  283.         in >> query.x >> query.y;
  284.     }
  285.     return data;
  286. }
  287.  
  288. std::vector<Data> Input(std::istream& in) {
  289.     size_t test_cnt;
  290.     in >> test_cnt;
  291.     std::vector<Data> tests(test_cnt);
  292.     for (auto& data : tests) {
  293.         data = InputData(in);
  294.     }
  295.     return tests;
  296. }
  297.  
  298. std::vector<std::vector<PointPos>> Tests(std::vector<Data> tests) {
  299.     std::vector<std::vector<PointPos> > ans;
  300.     for (auto& data : tests) {
  301.         BelongPoints solve;
  302.         solve.init(data);
  303.         ans.push_back(solve.MakeAns());
  304.     }
  305.     return ans;
  306. }
  307.  
  308. void Output(std::vector<std::vector<PointPos>> answers, std::ostream& out) {
  309.     for (auto& ans : answers) {
  310.         for (auto position : ans) {
  311.             std::string s;
  312.             switch (position) {
  313.             case INSIDE:
  314.                 s = "INSIDE\n";
  315.                 break;
  316.             case OUTSIDE:
  317.                 s = "OUTSIDE\n";
  318.                 break;
  319.             case BORDER:
  320.                 s = "BORDER\n";
  321.                 break;
  322.             default:
  323.                 break;
  324.             }
  325.             out << s;
  326.         }
  327.     }
  328. }
  329.  
  330. void solve(std::istream& in, std::ostream& out) {
  331.     auto tests = Input(in);
  332.     auto answer = Tests(tests);
  333.     Output(answer, out);
  334. }
  335.  
  336. int main() {
  337.     solve(std::cin, std::cout);
  338.     system("pause");
  339. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement