QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#309551 | #6403. Master of Polygon | chimucong | TL | 0ms | 3592kb | C++14 | 6.4kb | 2024-01-20 18:14:11 | 2024-01-20 18:14:11 |
Judging History
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...