QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#309551#6403. Master of PolygonchimucongTL 0ms3592kbC++146.4kb2024-01-20 18:14:112024-01-20 18:14:11

Judging History

你现在查看的是最新测评结果

  • [2024-01-20 18:14:11]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:3592kb
  • [2024-01-20 18:14:11]
  • 提交

answer

// A C++ program to check if two given line segments intersect
#include <algorithm>
#include <iostream>
#include <iterator>
#include <list>
#include <tuple>
#include <unordered_set>
#include <vector>

using namespace std;

struct Point {
    int x, y;
    Point(int x_, int y_) : x(x_), y(y_) {}
    bool operator<(const Point& rhs) {
        return x != rhs.x ? x < rhs.x : y < rhs.y;
    }
};

struct Seg {
    Point start, end;
    Seg(int xs, int ys, int xe, int ye) : start(xs, ys), end(xe, ye) {
        if (end < start)
            std::swap(start, end);
    }
};

// Given three collinear points p, q, r, the function checks if
// point q lies on line segment 'pr'
bool onSegment(const Point& p, const Point& q, const Point& r) {
    return (q.x <= max(p.x, r.x) && q.x >= min(p.x, r.x) && q.y <= max(p.y, r.y) && q.y >= min(p.y, r.y));
}

// To find orientation of ordered triplet (p, q, r).
// The function returns following values
// 0 --> p, q and r are collinear
// 1 --> Clockwise
// 2 --> Counterclockwise
int orientation(Point& p, Point& q, Point& r) {
    // See https://www.geeksforgeeks.org/orientation-3-ordered-points/
    // for details of below formula.
    int val = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y);

    if (val == 0)
        return 0;  // collinear

    return (val > 0) ? 1 : 2;  // clock or counterclock wise
}

// The main function that returns true if line segment 'p1q1'
// and 'p2q2' intersect.
bool doIntersect(Point& p1, Point& q1, Point& p2, Point& q2) {
    // Find the four orientations needed for general and
    // special cases
    int o1 = orientation(p1, q1, p2);
    int o2 = orientation(p1, q1, q2);
    int o3 = orientation(p2, q2, p1);
    int o4 = orientation(p2, q2, q1);

    // General case
    if (o1 != o2 && o3 != o4)
        return true;

    // Special Cases
    // p1, q1 and p2 are collinear and p2 lies on segment p1q1
    if (o1 == 0 && onSegment(p1, p2, q1))
        return true;

    // p1, q1 and q2 are collinear and q2 lies on segment p1q1
    if (o2 == 0 && onSegment(p1, q2, q1))
        return true;

    // p2, q2 and p1 are collinear and p1 lies on segment p2q2
    if (o3 == 0 && onSegment(p2, p1, q2))
        return true;

    // p2, q2 and q1 are collinear and q1 lies on segment p2q2
    if (o4 == 0 && onSegment(p2, q1, q2))
        return true;

    return false;  // Doesn't fall in any of the above cases
}

bool doIntersect(Seg& s1, Seg& s2) {
    return doIntersect(s1.start, s1.end, s2.start, s2.end);
}

// Driver program to test above functions
int main1() {
    struct Point p1 = {1, 1}, q1 = {10, 1};
    struct Point p2 = {1, 2}, q2 = {10, 2};

    doIntersect(p1, q1, p2, q2) ? cout << "Yes\n" : cout << "No\n";

    p1 = {10, 0}, q1 = {0, 10};
    p2 = {0, 0}, q2 = {10, 10};
    doIntersect(p1, q1, p2, q2) ? cout << "Yes\n" : cout << "No\n";

    p1 = {-5, -5}, q1 = {0, 0};
    p2 = {1, 1}, q2 = {10, 10};
    doIntersect(p1, q1, p2, q2) ? cout << "Yes\n" : cout << "No\n";

    return 0;
}

bool doIntersect(vector<Point>& vp, Point& a, Point& b) {
    for (int i = 0; i < vp.size(); i++) {
        if (doIntersect(vp[i], vp[i + 1 == vp.size() ? 0 : i + 1], a, b))
            return true;
    }
    return false;
}

using Event = std::tuple<int, int, Seg*>;

void print_vs(vector<Seg> & vs){
	printf("\n------\n");
	for(auto & itr :vs){
		printf("(%d, %d)->(%d, %d)\n",itr.start.x,itr.start.y,itr.end.x,itr.end.y);
	}
	printf("------\n\n");
}
int main() {
    int n, q;
    // vector<Point> vp;
    vector<Seg> vsp;
    vector<Seg> vsq;
    vector<Event> ve;
    while (cin >> n >> q) {
        ve.clear();
        ve.reserve((n + q) * 2);
		// cout << "test n: " << n << endl;
		// cout << "test q: " << q << endl;
        vector<bool> ret(q, false);
        {
            vsp.clear();
            vsp.reserve(n);
            int x0, y0;
            int x_prev, y_prev;
            for (int i = 0; i < n; i++) {
                if (i == 0) {
                    cin >> x0 >> y0;
                    x_prev = x0;
                    y_prev = y0;
                } else {
                    int x, y;
					cin >> x >> y;
                    vsp.emplace_back(x_prev, y_prev, x, y);
                    x_prev = x;
                    y_prev = y;
                }
                if (i == n - 1) {
                    vsp.emplace_back(x_prev, y_prev, x0, y0);
                }
            }
        }

        {
            vsq.clear();
            vsq.reserve(q);
            for (int i = 0; i < q; i++) {
                int x1, x2, y1, y2;
                cin >> x1 >> y1 >> x2 >> y2;
                vsq.emplace_back(x1, y1, x2, y2);
            }
        }

		// print_vs(vsp);
		// print_vs(vsq);
        for (auto& itr : vsp) {
            ve.emplace_back(itr.start.x, -1, &itr);
            ve.emplace_back(itr.end.x, 1, &itr);
        }
        for (auto& itr : vsq) {
            ve.emplace_back(itr.start.x, -1, &itr);
            ve.emplace_back(itr.end.x, 1, &itr);
        }
        std::sort(ve.begin(), ve.end(), [](Event& lhs, Event& rhs) {
            if (std::get<0>(lhs) != std::get<0>(rhs))
                return std::get<0>(lhs) < std::get<0>(rhs);
            if (std::get<1>(lhs) != std::get<1>(rhs))
                return std::get<1>(lhs) < std::get<1>(rhs);
            return std::get<2>(lhs) < std::get<2>(rhs);
        });
        std::unordered_set<Seg*> sp, sq;
        auto check = [&]() {
            for (auto* q_itr : sq) {
                for (auto* p_itr : sp) {
                    if (doIntersect(*q_itr, *p_itr)) {
                        ret[std::distance(&vsq[0], q_itr)] = true;
                        break;
                    }
                }
            }
        };
        for (auto& itr : ve) {
            auto& type = std::get<1>(itr);
            auto& addr = std::get<2>(itr);
            std::unordered_set<Seg*>* ps;
            if (addr >= &vsp.front() && addr <= &vsp.back()) {
                ps = &sp;
            } else {
                ps = &sq;
            }
            if (type == -1) {
                ps->emplace(addr);
            } else {
                check();
                ps->erase(addr);
            }
        }
        for (auto itr : ret) {
            printf(itr ? "YES\n" : "NO\n");
        }
    }

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3592kb

input:

4 6
1 1
4 1
4 4
1 4
0 2 2 0
0 1 1 1
0 0 5 5
2 2 4 2
2 2 3 2
5 1 0 2

output:

YES
YES
YES
YES
NO
YES

result:

ok 6 token(s): yes count is 5, no count is 1

Test #2:

score: -100
Time Limit Exceeded

input:

20 200000
8838 9219
12190 11292
15953 7581
16690 6159
21104 5484
8978 1076
4354 1065
1261 676
12684 14159
15469 22416
13493 28027
15531 26837
18253 26053
26444 24253
22160 19958
24879 12856
28793 22156
25300 10245
14749 15078
12946 13942
26544 28338 18806 21279
5592 29200 20935 25253
28189 17513 215...

output:


result: