If the line is N ( horizontal or vertical ), I need to find the complete intersection of these line segments, as well as the intersection of the line. My code is as follows:
using namespace std;
#define x second
#define y first
#define MAX 10000
typedef pair<int,int >point;
struct event
{
point p1,p2;
int type;
event() {};
event(point p1,point p2, int type) : p1(p1), p2(p2),type(type) {};
};
int n,e;
event events[MAX];
bool compare(event a, event b)
{
return a.p1.x<b.p1.x;
}
set<point >s;
int hv_intersection()
{
ll count=0;
for (ll i=0;i<e;++i)
{
event c = events[i];
if (c.type==0) s.insert(c.p1);
else if (c.type==1) s.erase(c.p2);
else
{
for (typeof(s.begin()) it=s.lower_bound(make_pair(c.p1.y,-1));it!=s.end() && it->y<=c.p2.y; it++)
{ printf("%d, %d\n", events[i].p1.x, it->y);
count++;
}
}
}
return count;
}
int main ()
{
scanf("%d", &n);
ll p1x,p1y,p2x,p2y;
for (int i=0;i<n;++i)
{
scanf("%d %d %d %d", &p1x, &p1y,&p2x, &p2y);
if(p1x==p2x)
{
events[e++]=event(make_pair(p1y,p1x),make_pair(p2y,p2x),2);
}
else
{
events[e++]=event(make_pair(p1y,p1x),make_pair(p2y,p2x),0);
events[e++]=event(make_pair(p2y,p2x),make_pair(p1y,p1x),1);
}
}
sort(events, events+e,compare);
int count= hv_intersection();
cout<<"count="<<count;
return 0;
}
For the following input:
5 // number of lines
0 0 0 3 // x1,y1,x2,y2
2 0 2 5
3 0 3 5
0 0 3 0
0 3 3 3
Output:
2, 0
2, 3
3, 0
3, 3
count=4
Now I can not figure out how to do the following:
1. The intersection should not be where the endpoint of both segments meet. One endpoint may lie on another line segment, although the value (3.0) is incorrect . Valid intersection points according to my conditions are:
(2,0) , (2,3), (3,3)
2. I want to calculate the number of intersections per line, that is, the desired result should be:
0 2 1 1 2
count=3
i.e.
0 0 0 3 has 0 intersection
2 0 2 5 has 2 intersections
3 0 3 5 has 1 intersection
0 0 3 0 has 1 intersection
0 3 3 3 has 2 intersections
Can someone help me fix these 2 errors in the code?