Task: | Line Segment Intersection |
Sender: | paulschulte |
Submission time: | 2024-11-06 22:23:35 +0200 |
Language: | C++ (C++17) |
Status: | READY |
Result: | ACCEPTED |
test | verdict | time | |
---|---|---|---|
#1 | ACCEPTED | 0.21 s | details |
#2 | ACCEPTED | 0.22 s | details |
#3 | ACCEPTED | 0.24 s | details |
#4 | ACCEPTED | 0.26 s | details |
#5 | ACCEPTED | 0.00 s | details |
#6 | ACCEPTED | 0.00 s | details |
Code
// ~/.vim/cpp_template.cpp#include <bits/stdc++.h>#include <iostream>#include <vector>#include <algorithm>#include <string>#include <limits>#define REP(i,a,b) for (int i = a; i < b; i++)// Type Aliases for 1D and 2D vectors with initialization#define vi(n, val) vector<int>(n, val) // 1D vector of ints with size n, initialized to val#define vll(n, val) vector<long long>(n, val) // 1D vector of long longs with size n, initialized to val#define ll long long#define vvi(n, m, val) vector<vector<int>>(n, vector<int>(m, val)) // 2D vector of ints (n x m), initialized to val#define vvll(n, m, val) vector<vector<long long>>(n, vector<long long>(m, val)) // 2D vector of long longs (n x m), initialized to val#define LL_INF std::numeric_limits<long long int>::max()#define INF std::numeric_limits<int>::max()using namespace std;template <typename T>void pV(const std::vector<T>& vec, const std::string& label = "Vector") {std::cout << label << ": [ ";for (const auto& elem : vec) {std::cout << elem << " ";}std::cout << "]" << std::endl;}void dfs(int s, vector<bool> *visited, vector<int> (*adj)[]) {if ((*visited)[s]) return;(*visited)[s] = true;// process node sfor (auto u: (*adj)[s]) {dfs(u, visited, adj);}}/*// DEPTH-FRIRST-SEARCHvector<int> adj[N];vector<bool> visited(N, false);int u, v;for(int i = 0; i < M;i++){cin >> u >> v;u--;v--;adj[u].push_back(v);adj[v].push_back(u);}*/vector<long long> dijkstra(int N, int x, vector<vector<pair<int,int>>> *adj){vector<bool> processed(N, false);vector<long long> distance(N, LL_INF);priority_queue<pair<long long,int>> q;//for (int i = 1; i <= n; i++) distance[i] = INF;distance[x] = 0;q.push({0,x});while (!q.empty()) {int a = q.top().second; q.pop();if (processed[a]) continue;processed[a] = true;for (auto u : (*adj)[a]) {int b = u.first, w = u.second;if (distance[a]+w < distance[b]) {distance[b] = distance[a]+w;q.push({-distance[b],b});}}}return distance;}/*DIJKSTRA//vector<vector<pair<int,int>>> adj(N, vector<pair<int, int>>(N));*/struct Point {long long x, y;};int oriet(Point p, Point q, Point r) {long long val = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y);if (val == 0) return 0;return (val > 0) ? 1 : 2;}bool onS(Point p, Point q, 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);}bool inter(Point p1, Point q1, Point p2, Point q2) {int o1 = oriet(p1, q1, p2);int o2 = oriet(p1, q1, q2);int o3 = oriet(p2, q2, p1);int o4 = oriet(p2, q2, q1);if (o1 != o2 && o3 != o4)return true;if (o1 == 0 && onS(p1, p2, q1)) return true;if (o2 == 0 && onS(p1, q2, q1)) return true;if (o3 == 0 && onS(p2, p1, q2)) return true;if (o4 == 0 && onS(p2, q1, q2)) return true;return false;}int main() {ios::sync_with_stdio(0);cin.tie(0);// Your code starts hereint t;cin >> t;REP(i, 0, t){Point p1, q1, p2, q2;cin >> p1.x >> p1.y >> q1.x >> q1.y >> p2.x >> p2.y >> q2.x >> q2.y;if(inter(p1, q1, p2, q2)){cout << "YES" << endl;}else{cout << "NO" << endl;}}return 0;}
Test details
Test 1
Verdict: ACCEPTED
input |
---|
100000 9 7 1 8 8 -5 0 2 10 1 -1 2 -4 1 -7 3 10 2 -8 6 1 2 2 -1 -10 1 9 -7 4 -3 -5 0 ... |
correct output |
---|
NO NO NO NO NO ... |
user output |
---|
NO NO NO NO NO ... Truncated |
Test 2
Verdict: ACCEPTED
input |
---|
100000 81 745 -967 768 -451 -490 -454... |
correct output |
---|
NO NO YES NO YES ... |
user output |
---|
NO NO YES NO YES ... Truncated |
Test 3
Verdict: ACCEPTED
input |
---|
100000 492853 -452834 -657156 -282543... |
correct output |
---|
YES YES NO YES YES ... |
user output |
---|
YES YES NO YES YES ... Truncated |
Test 4
Verdict: ACCEPTED
input |
---|
100000 788522666 939776556 -831492125... |
correct output |
---|
NO NO NO NO NO ... |
user output |
---|
NO NO NO NO NO ... Truncated |
Test 5
Verdict: ACCEPTED
input |
---|
1 1 6 6 6 4 4 1000000000 1000000... |
correct output |
---|
YES |
user output |
---|
YES |
Test 6
Verdict: ACCEPTED
input |
---|
1 -1000000000 1000000000 9999999... |
correct output |
---|
NO |
user output |
---|
NO |