Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <string>
- #include <vector>
- #include <set>
- #include <map>
- #include <algorithm>
- class Point {
- public:
- double x;
- double y;
- Point() = default;
- Point(double x, double y) : x(x) , y(y)
- {}
- };
- double cr_prod(const Point& a, const Point& b) {
- return a.x * b.y - b.x * a.y;
- }
- enum PointPos {
- OUTSIDE,
- INSIDE,
- BORDER
- };
- enum SegmentPos {
- ABOVE,
- BELOW
- };
- class Segment {
- private:
- Point begin_;
- Point end_;
- SegmentPos pos_;
- public:
- Segment() = default;
- Segment(Point begin, Point end, SegmentPos pos) : begin_(begin), end_(end), pos_(pos)
- {}
- Segment(Point pt) : Segment(pt, pt, ABOVE)
- {}
- const Point& begin() const { return begin_; }
- const Point& end() const { return end_; }
- SegmentPos pos() const { return pos_; }
- bool is_vertical() const {
- if (begin_.x == end_.x) return true;
- return false;
- }
- double get_y(double x) const {
- if (is_vertical()) return begin_.y;
- return begin_.y + (x - begin_.x) * (end_.y - begin_.y) / (end_.x - begin_.x);
- }
- };
- enum EventOrder {
- OPEN,
- CLOSE,
- QUERY
- };
- struct Event {
- double loc;
- EventOrder type;
- size_t id;
- Event(double loc, EventOrder type, size_t id) : loc(loc), type(type), id(id)
- {}
- Event(double loc, EventOrder type) : Event(loc, type, SIZE_MAX)
- {}
- };
- struct CompOpenQueryClose {
- bool operator() (const Event& a, const Event& b) const{
- if (a.loc != b.loc) {
- return a.loc < b.loc;
- }
- static std::vector<EventOrder> order = { EventOrder::OPEN, EventOrder::QUERY, EventOrder::CLOSE };
- return std::find(order.begin(), order.end(), a.type) <
- std::find(order.begin(), order.end(), b.type);
- }
- };
- struct CompCloseOpenQuery {
- bool operator ()(const Event& a, const Event& b) const{
- if (a.loc != b.loc) {
- return a.loc < b.loc;
- }
- static std::vector<EventOrder> order = { EventOrder::CLOSE, EventOrder::OPEN, EventOrder::QUERY };
- return std::find(order.begin(), order.end(), a.type) < std::find(order.begin(), order.end(), b.type);
- }
- };
- struct CompPoint {
- bool operator ()(const Point& a, const Point& b) const{
- if (std::make_pair(a.x, a.y) < std::make_pair(b.x, b.y)) return true;
- return false;
- }
- };
- struct CompSeg {
- bool operator ()(const Segment& a, const Segment& b) const{
- double intersec_begin = std::max(a.begin().x, b.begin().x);
- double intersec_end = std::min(a.end().x, b.end().x);
- std::pair< double, double > ord_a = std::make_pair(a.get_y(intersec_begin), a.get_y(intersec_end));
- std::pair< double, double > ord_b = std::make_pair(b.get_y(intersec_begin), b.get_y(intersec_end));
- return ord_a < ord_b;
- }
- };
- struct Data {
- std::vector<Point> queries;
- std::vector <Point> vertices;
- };
- class BelongPoints {
- public:
- void init(const Data& data) {
- ver_ = data.vertices;
- qr_ = data.queries;
- }
- std::vector<PointPos> MakeAns() {
- ans_.assign(qr_.size(), PointPos::OUTSIDE);
- MakeSeg();
- OnVertex();
- VerticalSegments();
- std::vector<Event> events;
- for (size_t i = 0; i < seg_.size(); ++i) {
- if (!seg_[i].is_vertical()) {
- events.emplace_back(seg_[i].begin().x, EventOrder::OPEN, i);
- events.emplace_back(seg_[i].end().x, EventOrder::CLOSE, i);
- }
- }
- for (size_t i = 0; i < qr_.size(); ++i) {
- events.emplace_back(qr_[i].x, EventOrder::QUERY, i);
- }
- sort(events.begin(), events.end(), CompCloseOpenQuery());
- std::multiset<Segment, CompSeg> opened_edges;
- for (const Event& event : events) {
- switch (event.type) {
- case EventOrder::OPEN:
- opened_edges.insert(seg_[event.id]);
- break;
- case EventOrder::CLOSE:
- opened_edges.erase(opened_edges.find(seg_[event.id]));
- break;
- case EventOrder::QUERY:
- Segment query(qr_[event.id]);
- auto it = opened_edges.lower_bound(query);
- if (it != opened_edges.end() && it->get_y(qr_[event.id].x) == qr_[event.id].y) {
- UpdateAnswer(event.id, BORDER);
- }
- if (it != opened_edges.begin()) {
- --it;
- if (it->pos() == ABOVE) {
- UpdateAnswer(event.id, INSIDE);
- }
- }
- }
- }
- return ans_;
- }
- private:
- std::vector<Point> qr_, ver_;
- std::vector<Segment> seg_;
- std::vector<PointPos> ans_;
- void UpdateAnswer(size_t id, PointPos pos) {
- ans_[id] = std::max(ans_[id], pos);
- }
- bool SignOrientedArea() const {
- double s = 0;
- for (size_t i = 0; i < ver_.size(); ++i) {
- s += cr_prod(ver_[i], ver_[(i + 1) % ver_.size()]);
- }
- return s >= 0;
- }
- void MakeSeg() {
- seg_.resize(ver_.size());
- for (size_t i = 0; i < ver_.size(); ++i) {
- Point begin = ver_[i];
- Point end = ver_[(i + 1) % ver_.size()];
- bool cmp = CompPoint()(begin, end);
- SegmentPos pos = cmp ^ (!SignOrientedArea()) ? ABOVE : BELOW;
- if (!cmp) {
- std::swap(begin, end);
- }
- seg_[i] = Segment(begin, end, pos);
- }
- }
- void BelongVerticalSegment(const std::vector<Segment>& segments, const std::vector<size_t>& queries) {
- std::vector<Event> events;
- for (const Segment& seg : segments) {
- events.emplace_back(std::min(seg.begin().y, seg.end().y), EventOrder::OPEN);
- events.emplace_back(std::max(seg.begin().y, seg.end().y), EventOrder::CLOSE);
- }
- for (size_t id : queries) {
- events.emplace_back(qr_[id].y, EventOrder::QUERY, id);
- }
- sort(events.begin(), events.end(), CompOpenQueryClose());
- size_t cnt = 0;
- for (const Event& event : events) {
- switch (event.type) {
- case EventOrder::OPEN:
- cnt++;
- break;
- case EventOrder::CLOSE:
- cnt--;
- break;
- case EventOrder::QUERY:
- if (cnt) UpdateAnswer(event.id, BORDER);
- }
- }
- }
- void VerticalSegments() {
- std::map<double, std::vector<Segment>> vertical;
- for (const Segment& seg : seg_) {
- if (seg.is_vertical()) {
- vertical[seg.begin().x].push_back(seg);
- }
- }
- std::map<double, std::vector<size_t>> queries;
- for (size_t i = 0; i < qr_.size(); ++i) {
- queries[qr_[i].x].push_back(i);
- }
- for (auto& i : vertical) {
- BelongVerticalSegment(i.second, queries[i.first]);
- }
- }
- void OnVertex() {
- std::set<Point, CompPoint> ver(ver_.begin(), ver_.end());
- for (size_t i = 0; i < qr_.size(); ++i) {
- if (ver.count(qr_[i])) {
- UpdateAnswer(i, BORDER);
- }
- }
- }
- };
- Data InputData(std::istream& in) {
- Data data;
- size_t cnt_vert;
- size_t cnt_qr;
- in >> cnt_vert;
- data.vertices.resize(cnt_vert);
- for (auto& vertex : data.vertices) {
- in >> vertex.x >> vertex.y;
- }
- in >> cnt_qr;
- data.queries.resize(cnt_qr);
- for (auto& query : data.queries) {
- in >> query.x >> query.y;
- }
- return data;
- }
- std::vector<Data> Input(std::istream& in) {
- size_t test_cnt;
- in >> test_cnt;
- std::vector<Data> tests(test_cnt);
- for (auto& data : tests) {
- data = InputData(in);
- }
- return tests;
- }
- std::vector<std::vector<PointPos>> Tests(std::vector<Data> tests) {
- std::vector<std::vector<PointPos> > ans;
- for (auto& data : tests) {
- BelongPoints solve;
- solve.init(data);
- ans.push_back(solve.MakeAns());
- }
- return ans;
- }
- void Output(std::vector<std::vector<PointPos>> answers, std::ostream& out) {
- for (auto& ans : answers) {
- for (auto position : ans) {
- std::string s;
- switch (position) {
- case INSIDE:
- s = "INSIDE\n";
- break;
- case OUTSIDE:
- s = "OUTSIDE\n";
- break;
- case BORDER:
- s = "BORDER\n";
- break;
- default:
- break;
- }
- out << s;
- }
- }
- }
- void solve(std::istream& in, std::ostream& out) {
- auto tests = Input(in);
- auto answer = Tests(tests);
- Output(answer, out);
- }
- int main() {
- solve(std::cin, std::cout);
- system("pause");
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement