273

Line Segment Intersection:

1. General Case:
a) (p1, q1, p2) and (p1, q1, q2) have different orientations and
b) (p2, q2, p1) and (p2, q2, q1) have different orientations

2. Special Case
a) (p1, q1, p2), (p1, q1, q2), (p2, q2, p1), and (p2, q2, q1) are all collinear and
b) the x-projections of (p1, q1) and (p2, q2) intersect
c) the y-projections of (p1, q1) and (p2, q2) intersect

To solve the problem floyd warshall algorithm is used.

More

#include <iostream>

using namespace std;

struct Point
{
    int x;
    int y;
};

Point P[50];
Point Q[50];
bool gr[50][50];

int orient(Point p,Point q,Point r)
{
	//slope of pq - slope of qr
	double v = ((p.y-q.y)*(q.x-r.x) - (q.y-r.y)*(p.x-q.x));
	if(v==0)
	return 0;
	else if(v>0)
	return 1;
	else if(v<0)
	return 2;
}

bool onlineSeg(Point p,Point q,Point r)
{
	if (r.x <= max(p.x, q.x) && r.x >= min(p.x, q.x) &&
        r.y <= max(p.y, q.y) && r.y >= min(p.y, q.y))
       return true;

    return false;
}

//y1-mx1-cc =0;
bool isConnect(int i,int j)
{
	int a,b,c,d;
	Point p1,q1,p2,q2;
	p1 = P[i];
	q1 = Q[i];
	p2 = P[j];
	q2 = Q[j];

	a = orient(p1,q1,p2);
	b = orient(p1,q1,q2);
	c = orient(p2,q2,p1);
	d = orient(p2,q2,q1);

	if(a!=b && c!=d)
	return 1;
	if(a == 0 && onlineSeg(p1,q1,p2))//p2 inside of p1q1
	return 1;
	if(b == 0 && onlineSeg(p1,q1,q2))//q2 inside of p1q1
	return 1;
	if(c == 0 && onlineSeg(p2,q2,p1))//q1 inside of p2q2
	return 1;
	if(d == 0 && onlineSeg(p2,q2,q1))//q1 inside of p2q2
	return 1;

	return 0;
}

int main()
{
	int t,n;
	double a,b,c,d;
	bool f=1;
	cin>>t;

	while(t--)
	{
		cin>>n;
		for(int i=0;i<n;i++)
			for(int j=0;j<n;j++)
			{
				if(i==j)
				gr[i][j]=1;
				else
				gr[i][j]=0;
			}
		for(int i=0;i<n;i++)
		{
			cin>>a>>b>>c>>d;
			P[i].x =a;P[i].y =b;
			Q[i].x =c;Q[i].y =d;
		}

		for(int i=0;i<n;i++)
		{
			for(int j=i+1;j<n;j++)
			{
				if(isConnect(i,j))
				{
					gr[i][j]=1;
					gr[j][i]=1;
				}
			}
		}

		for(int k=0;k<n;k++)
		{
			for(int i=0;i<n;i++)
			{
				for(int j=0;j<n;j++)
				{
					if(!gr[i][j] && i!=j && j!=k)
						gr[i][j]=gr[i][k] && gr[k][j];
				}
			}
		}

		int p,q;
		int cnt=0;
		while(cin>>p)
		{
			cin>>q;
			if(p+q==0)
			break;
			//cout<<gr[p-1][q-1]<<"\n";
			if(!f)
			{
				if(cnt==0)
				cout<<"\n";
				cnt =1;
			}
			if(gr[p-1][q-1])
			cout<<"CONNECTED\n";
			else
			cout<<"NOT CONNECTED\n";
		}
		f = 0;
	}//while loop

	return 0;
}