Moving Segments | CodeChef
i was trying to solve above problem. i have come up with a solution but its giving wrong answer. i am not able to find out why it is wrong.
i will describe my approach.
so two line segments that have different velocities will be far apart after the given time t.
so the remaining ones are the line segments that have same velocities(2 line segments of velocity 3, 4 line segments of velocity 1 etc).
among line segments having same velocity if they are non intersecting then they will not intersect at after given time t.
so the line segments of concern are intersecting line segments having same velocity.
so if three of more line segments intersect with each other (every pair) then they will intersect even after given time t.
so i reduced the problem to a graph.
where each node is a line segment and two nodes are connected by an edge if they have same velocity and they are intersecting. if this graph has a cycle then our answer is NO else our answer is YES.
can any one point out where i am wrong? i am not able to find out.
Thank you for replying. you can find my Implementation below.
#include <bits/stdc++.h>
using namespace std;
bool ls_intersect(vector<vector<int>> &arr, int a, int b);
bool has_cycle(vector<vector<int>> &arr, int curr_node, vector<bool> &visited, int parent);
int main()
{
int t;
cin >> t;
while (t--)
{
int n;
cin >> n;
vector<vector<int>> ls(n, vector<int>(3));
vector<vector<int>> g(n);
for(auto &l: ls){
cin >> l[0] >> l[1] >> l[2];
}
for(int i = 0; i < n; i++){
for(int j = i+1; j < n; j++){
int xa = ls[i][0], xb = ls[i][1];
int ya = ls[j][0], yb = ls[j][1];
if(ls_intersect(ls, i, j) && ls[i][2] == ls[j][2]){
g[i].push_back(j);
g[j].push_back(i);
}
}
}
// for(int i = 0; i < n; i++){
// cout << i << ": ";
// for(auto x: arr[i]){
// cout << x << " " ;
// }
// cout << endl;
// }
// check if there is a cycle in arr if there is then output NO else output YES
vector<bool> visited(n, false);
bool hc = false;
for(int i = 0; i < n; i++){
if(visited[i]) continue;
if (has_cycle(g, i, visited, -1)){
hc = true; break;
}
}
// cout << endl;
if(hc){
cout << "No\n";
} else{
cout << "Yes\n";
}
}
return 0;
}
bool ls_intersect(vector<vector<int>> &arr, int a, int b)
{
int xa = arr[a][0], xb = arr[a][1];
int ya = arr[b][0], yb = arr[b][1];
if (xa <= ya)
{
if (ya <= xb)
return true;
else
return false;
}
else
{
if (xa <= yb)
return true;
else
return false;
}
}
bool has_cycle(vector<vector<int>> &arr, int curr_node, vector<bool> &visited, int parent)
{
// cout << "curr_node: " << curr_node << endl;
if (visited[curr_node])
return true;
visited[curr_node] = true;
for (auto x : arr[curr_node])
{
if (x == parent)
continue;
if (visited[x]){
return true; // you are revisiting a visited node that is not parent;
}
// else explore further;
if (has_cycle(arr, x, visited, curr_node))
{
return true;
}
}
return false;
}
