Before revision:  Moreover, we remark that if the straight lines are not given, then the problem becomes \exists\mathbb{R
After revision:  Using the reduction we described, we also show that this problem is NP-complete when the given lines are only parallel to x-axis (and one another). We obtain those results using the idea of the logic engine introduced by Bhatt and Cosmadakis in 1987.