Code: Select all
#include <bits/stdc++.h>
#define EPS 1e-9
using namespace std;
struct point
{
double x,y;
point()
{
x=0;
y=0;
}
};
struct line//line is represented in form ax+by+c=0
{
double a,b,c;
line()
{
a=0;
b=0;
c=0;
}
};
line point_to_line(point p1,point p2)
{
//always in the form ax+by+c=0
line l;
//not in canonical form.a,b,c, is double
if(p1.x==p2.x)
{
l.a=1.0;
l.b=0.0;
l.c=-p1.x;
}
else
{
l.a=-(double)(p1.y-p2.y)/(p1.x-p2.x);
l.b=1.0;
l.c=-(double)(l.a*p1.x)-(l.b*p1.y);
}
return l;
}
// To find orientation of ordered triplet (p, q, r).
// The function returns following values
// 0 --> p, q and r are colinear
// 1 --> Clockwise
// 2 --> Counterclockwise
int orientation(point p, point q, point r)
{
// See 10th slides from following link for derivation of the formula
// http://www.dcs.gla.ac.uk/~pat/52233/slides/Geometry1x1.pdf
int val = (q.y - p.y) * (r.x - q.x) -
(q.x - p.x) * (r.y - q.y);
if (val == 0) return 0; // colinear
return (val > 0)? 1: 2; // clock or counterclock wise
}
// point q lies on line segment 'pr'
bool onSegment(point p, point q, point r)
{
if(orientation(p,q,r)!=0)//not colinear
return false;
if (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))
return true;
return false;
}
//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 colinear and p2 lies on segment p1q1
if (o1 == 0 && onSegment(p1, p2, q1)) return true;
// p1, q1 and p2 are colinear and q2 lies on segment p1q1
if (o2 == 0 && onSegment(p1, q2, q1)) return true;
// p2, q2 and p1 are colinear and p1 lies on segment p2q2
if (o3 == 0 && onSegment(p2, p1, q2)) return true;
// p2, q2 and q1 are colinear 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 areparallel(line l1,line l2)
{
return (fabs(l1.a-l2.a)<EPS && fabs(l1.b-l2.b)<EPS);
}
bool aresame(line l1,line l2)
{
return (areparallel(l1,l2)&&(fabs(l1.c-l2.c)<EPS));
}
bool does_intersect(line l1,line l2,point *p)
{
if(aresame(l1,l2))
return false;
if(areparallel(l1,l2))
return false;
p->x=(l2.b*l1.c-l1.b*l2.c)/(l2.a*l1.b-l1.a*l2.b);
if(fabs(l1.b>EPS))//special case for vertical line to avoid division by zero
{
p->y=-(l1.a*p->x+l1.c)/l1.b;
}
else
{
p->y=-(l2.a*p->x+l2.c)/l2.b;
}
return true;
}
struct line_segment
{
double y;
int line_id;
line_segment()
{
y=0;
line_id=0;
}
//bool operator<(const record& rhs, const record& next)
};
bool operator<(const line_segment& l1,const line_segment& l2)
{
if(fabs(l1.y-l2.y)<EPS)
return l1.line_id<l2.line_id;//multiple line can start at same point
return l1.y>l2.y;
}
struct event_point
{
int label;//start(1)/intersection(2)/end(3)
int corresponding_line;//relevant if point is start point or end point
int line1,line2;//relevant with intersection point
double x,y;
event_point()
{
x=0;
y=0;
corresponding_line=0;
line1=0;
line2=0;
}
};
bool operator<(const event_point& ev1,const event_point& ev2)
{
if(fabs(ev1.x-ev2.x)<EPS)
{
if(ev1.label==ev2.label)
{
//will process nodes from top to bottom
return ev1.y<ev2.y;
}
//if have same x coordinate want to sort according to start point(1),intersection point(2),end point (3)
return ev1.label>ev2.label;
}
else
return ev1.x>ev2.x;//lowest x value comes first.
}
set<line_segment>::iterator lsit[700];
struct ans
{
int line1,line2;
point intersecting_point;
ans()
{
line1=0;
line2=0;
intersecting_point.x=0;
intersecting_point.y=0;
}
};
bool operator<(const ans& p,const ans& q)
{
if(p.line1==q.line1)
return p.line2<q.line2;
return p.line1<q.line1;
}
int main()
{
int i,j,n,t,m;
//freopen("output.txt","w",stdout);
cin>>t;
while(t--)
{
set<int>answer;
cin>>m;
point p1,q1,p2,q2,r;
line l1,l2;
priority_queue<event_point>pq;
/*VL will hold points of line segment.first of the pair is left most and
second one is right most.If vertical line then first topmost then bottom
*/
vector<pair<point,point> >VL;
VL.resize(m+5);
event_point ev1,intersection;
line_segment ls,ls1,ls2;
ans ANS;
for(i=1;i<=m;i++)
{
cin>>p1.x>>p1.y>>p2.x>>p2.y;
if(p1.x>p2.x)
{
swap(p1,p2);
}
else if(fabs(p1.x-p2.x)<EPS&&p1.y<p2.y)
{
swap(p1,p2);
}
VL[i]=make_pair(p1,p2);
ev1.x=p1.x;
ev1.y=p1.y;
ev1.label=1;//start point
ev1.corresponding_line=i;
pq.push(ev1);
ev1.x=p2.x;
ev1.y=p2.y;
ev1.label=3;//end point
ev1.corresponding_line=i;
pq.push(ev1);
}
set<line_segment>lset;
set<line_segment>::iterator lsetitend,prev_point,next_point,above,below,it,tmp1,tmp2,tmp;
set<ans>intersecting_lines;
set<ans>::iterator ansit;
pair<set<line_segment>::iterator,bool>sp;
/*
pair::first set to an iterator pointing to either the newly inserted element
or to the equivalent element already in the set. The pair::second element in
the pair is set to true if a new element was inserted or false if an equivalent
element already existed. From C++ reference, return value of set insertion
*/
while(!pq.empty())
{
event_point ev=pq.top();
pq.pop();
if(ev.label==1)//start point
{
ls.line_id=ev.corresponding_line;
ls.y=ev.y;
sp=lset.insert(ls);
lsit[ls.line_id]=sp.first;
if(sp.first!=lset.begin())
{
prev_point=sp.first;
prev_point--;
i=(*prev_point).line_id;
j=(*sp.first).line_id;
p1=VL[i].first;
q1=VL[i].second;
p2=VL[j].first;
q2=VL[j].second;
if(doIntersect(p1,q1,p2,q2))
{
l1=point_to_line(p1,q1);
l2=point_to_line(p2,q2);
//must intersect and intersection point is set to r
does_intersect(l1,l2,&r);
ANS.intersecting_point=r;
if(i>j)
swap(i,j);
ANS.line1=i;
ANS.line2=j;
intersecting_lines.insert(ANS);
intersection.label=2;
intersection.line1=i;
intersection.line2=j;
intersection.x=r.x;
intersection.y=r.y;
pq.push(intersection);
}
}
lsetitend=lset.end();
lsetitend--;
if(sp.first!=lsetitend)
{
next_point=sp.first;
next_point++;
i=(*next_point).line_id;
j=(*sp.first).line_id;
p1=VL[i].first;
q1=VL[i].second;
p2=VL[j].first;
q2=VL[j].second;
if(doIntersect(p1,q1,p2,q2))
{
l1=point_to_line(p1,q1);
l2=point_to_line(p2,q2);
//must intersect and intersection point is set to r
does_intersect(l1,l2,&r);
ANS.intersecting_point=r;
if(i>j)
swap(i,j);
ANS.line1=i;
ANS.line2=j;
intersecting_lines.insert(ANS);
event_point intersection;
intersection.label=2;
intersection.line1=i;
intersection.line2=j;
intersection.x=r.x;
intersection.y=r.y;
pq.push(intersection);
}
}
}
else if(ev.label==2)
{
i=ev.line1;
j=ev.line2;
above=lsit[i];
below=lsit[j];
ls1=*above;
ls2=*below;
// they were sorted according to start point y co ordinate now they will be sorted according to right end point y coordinate
ls1.y=VL[i].second.y;
ls2.y=VL[j].second.y;
lset.erase(above);
if(above!=below)
lset.erase(below);
sp=lset.insert(ls1);
above=sp.first;
lsit[i]=sp.first;
sp=lset.insert(ls2);
lsit[j]=sp.first;
below=sp.first;
if(above!=lset.begin())
{
tmp1=above;
tmp1--;
ls1=*tmp1;
ls2=*above;
i=ls1.line_id;
j=ls2.line_id;
p1=VL[i].first;
q1=VL[i].second;
p2=VL[j].first;
q2=VL[j].second;
if(doIntersect(p1,q1,p2,q2))
{
l1=point_to_line(p1,q1);
l2=point_to_line(p2,q2);
//must intersect and intersection point is set to r
does_intersect(l1,l2,&r);
ANS.intersecting_point=r;
if(i>j)
swap(i,j);
ANS.line1=i;
ANS.line2=j;
if(intersecting_lines.find(ANS)==intersecting_lines.end())
{
intersecting_lines.insert(ANS);
intersection.label=2;
intersection.line1=i;
intersection.line2=j;
intersection.x=r.x;
intersection.y=r.y;
pq.push(intersection);
}
}
}
lsetitend=lset.end();
lsetitend--;
if(above!=lsetitend)
{
tmp1=above;
tmp1++;
ls1=*tmp1;
ls2=*above;
i=ls1.line_id;
j=ls2.line_id;
p1=VL[i].first;
q1=VL[i].second;
p2=VL[j].first;
q2=VL[j].second;
if(doIntersect(p1,q1,p2,q2))
{
l1=point_to_line(p1,q1);
l2=point_to_line(p2,q2);
//must intersect and intersection point is set to r
does_intersect(l1,l2,&r);
ANS.intersecting_point=r;
if(i>j)
swap(i,j);
ANS.line1=i;
ANS.line2=j;
if(intersecting_lines.find(ANS)==intersecting_lines.end())
{
intersecting_lines.insert(ANS);
intersection.label=2;
intersection.line1=i;
intersection.line2=j;
intersection.x=r.x;
intersection.y=r.y;
pq.push(intersection);
}
}
}
if(below!=lset.begin())
{
tmp1=below;
tmp1--;
ls1=*tmp1;
ls2=*below;
i=ls1.line_id;
j=ls2.line_id;
p1=VL[i].first;
q1=VL[i].second;
p2=VL[j].first;
q2=VL[j].second;
if(doIntersect(p1,q1,p2,q2))
{
line l1,l2;
l1=point_to_line(p1,q1);
l2=point_to_line(p2,q2);
point r;
//must intersect and intersection point is set to r
does_intersect(l1,l2,&r);
ans ANS;
ANS.intersecting_point=r;
if(i>j)
swap(i,j);
ANS.line1=i;
ANS.line2=j;
if(intersecting_lines.find(ANS)==intersecting_lines.end())
{
intersecting_lines.insert(ANS);
event_point intersection;
intersection.label=2;
intersection.line1=i;
intersection.line2=j;
intersection.x=r.x;
intersection.y=r.y;
pq.push(intersection);
}
}
}
lsetitend=lset.end();
lsetitend--;
if(below!=lsetitend)
{
tmp1=below;
tmp1++;
ls1=*tmp1;
ls2=*below;
i=ls1.line_id;
j=ls2.line_id;
p1=VL[i].first;
q1=VL[i].second;
p2=VL[j].first;
q2=VL[j].second;
if(doIntersect(p1,q1,p2,q2))
{
l1=point_to_line(p1,q1);
l2=point_to_line(p2,q2);
point r;
//must intersect and intersection point is set to r
does_intersect(l1,l2,&r);
ANS.intersecting_point=r;
if(i>j)
swap(i,j);
ANS.line1=i;
ANS.line2=j;
if(intersecting_lines.find(ANS)==intersecting_lines.end())
{
intersecting_lines.insert(ANS);
event_point intersection;
intersection.label=2;
intersection.line1=i;
intersection.line2=j;
intersection.x=r.x;
intersection.y=r.y;
pq.push(intersection);
}
}
}
}
else if(ev.label==3)
{
int sz=lset.size();
i=0;
i=ev.corresponding_line;
tmp=lsit[i];
lsetitend=lset.end();
lsetitend--;
if(tmp!=lset.begin()&&tmp!=lsetitend)
{
lset.erase(tmp);
above=tmp;
above--;
below=tmp;
below++;
ls1=*above;
ls2=*below;
i=ls1.line_id;
j=ls2.line_id;
p1=VL[i].first;
q1=VL[i].second;
p2=VL[j].first;
q2=VL[j].second;
if(doIntersect(p1,q1,p2,q2))
{
l1=point_to_line(p1,q1);
l2=point_to_line(p2,q2);
point r;
//must intersect and intersection point is set to r
does_intersect(l1,l2,&r);
//ANS.intersecting_point=r;
if(i>j)
swap(i,j);
ANS.line1=i;
ANS.line2=j;
if(intersecting_lines.find(ANS)==intersecting_lines.end())
{
intersecting_lines.insert(ANS);
event_point intersection;
intersection.label=2;
intersection.line1=i;
intersection.line2=j;
intersection.x=r.x;
intersection.y=r.y;
pq.push(intersection);
}
}
}
else
{
lset.erase(tmp);
}
}
}
for(ansit=intersecting_lines.begin();ansit!=intersecting_lines.end();ansit++)
{
ANS=*ansit;
answer.insert(ANS.line1);
answer.insert(ANS.line2);
}
//cout<<answer.size()<<endl;
cout<<m-answer.size()<<endl;
}
return 0;
}