Stuff

#include <iostream.h>#define MAX 205struct ditch{	int x1,x2,y1,y2;};struct town{	char name[23];	int x,y;};struct town* towns;struct ditch* ditches;int n,m;int vmat[MAX][MAX],visited[MAX],prev[MAX],*q;int min(int x,int y){	return x > y ? y : x;}int max(int x,int y){	return x < y ? y : x;}int onepointcase(struct town a,struct town b,struct ditch c,int flag){	float A1,B1,C1,A2,B2,C2;	int minx,miny,maxx,maxy;	//flag = 1 indicates a and b are same --> so its a single point and now two different points	if(flag){		minx = min(c.x1,c.x2);		maxx = minx == c.x1 ? c.x2 : c.x1;		miny = min(c.y1,c.y2);		maxy = miny == c.y1 ? c.y2 : c.y1;		A2 = c.y2 - c.y1,B2 = c.x1 - c.x2,C2 = (-(c.y1*(c.x2 - c.x1))) + (c.x1*(c.y2 - c.y1));		return (((A2 * a.x) + (B2* a.y) == C2) && a.x >= minx && a.x <= maxx && a.y >= miny && a.y <= maxy) ? 1 : 0;	}	minx = min(a.x,b.x);	maxx = minx == a.x ? b.x : a.x;	miny = min(a.y,b.y);	maxy = miny == a.y ? b.y : a.y;	A1 = b.y - a.y,B1 = a.x - b.x,C1 = (-(a.y*(b.x - a.x))) + (a.x*(b.y - a.y));	return (((A1 * c.x1) + (B1 * c.y1) == C1)&& c.x1 >= minx && c.x1 <= maxx && c.y1 >= miny && c.y1 <= maxy) ? 1 : 0;}int ifIntersect(struct town a,struct town b,struct ditch c){		if((a.x == b.x && a.y == b.y) || (c.x1 == c.x2 && c.y1 == c.y2))		return onepointcase(a,b,c,a.x == b.x && a.y == b.y ? 1 : 0);	//equation of straight line is	//x(y2 - y1) - y(x2 - x1) = x1(y2 - y1) + y1(x2 - x1)	//A = coeffiecient of x,B = coeff of y,C = constant	float A1,B1,C1,A2,B2,C2;	A1 = b.y - a.y,B1 = a.x - b.x,C1 = (-(a.y*(b.x - a.x))) + (a.x*(b.y - a.y));	A2 = c.y2 - c.y1,B2 = c.x1 - c.x2,C2 = (-(c.y1*(c.x2 - c.x1))) + (c.x1*(c.y2 - c.y1));	float del,delx,dely;	del = (A1*B2) - (A2*B1),delx = (C1*B2) - (C2*B1),dely = (A1*C2) - (A2*C1);	if(!del)		return 0;	float x,y;	x = delx/del;	y = dely/del;	//if(x,y) is any one of the endpoints of the ditch return false	/*if(x == c.x1 && y == c.y1)		return 0;	if(x == c.x2 && y == c.y2)		return 0;	*/	int minx,miny,maxx,maxy;	minx = min(a.x,b.x);	maxx = minx == a.x ? b.x : a.x;	miny = min(a.y,b.y);	maxy = miny == a.y ? b.y : a.y;	//if(x >= min(a.x,b.x) && x <= max(a.x,b.x) && y >= min(a.y,b.y) && y <= max(a.y,b.y) && x >= min(c.x1,c.x2) && x <= max(c.x1,c.x2) && y >= min(c.y1,c.y2) && y <= max(c.y1,c.y2))	if(x >= minx && x <= maxx && y >= miny && y <= maxy){		minx = min(c.x1,c.x2);		maxx = minx == c.x1 ? c.x2 : c.x1;		miny = min(c.y1,c.y2);		maxy = miny == c.y1 ? c.y2 : c.y1;		if(x >= minx && x <= maxx && y >= miny && y <= maxy)			return 1;	} 	return 0;}void construct_matrix(){	int i = 0,j = 0,intersects = 0,k = 0;	for(i = 0;i < n;i++)		for(j = i+1;j < n;j++){			intersects = 0;			for(k = 0;k < m && !(intersects = ifIntersect(towns[i],towns[j],ditches[k]));k++)				;			if(!intersects)				vmat[i][j] = vmat[j][i] = 1;		}}int buildSpanningTree(){	//normal BFS	int head = 0,tail = 0,temp,i = 0;	q = new int[MAX];	q[tail++] = 0;//start with vertex 0	prev[0] = -1;	visited[0] = 1;	while(head < tail){		temp = q[head++];		for(i = 0;i < n;i++)			if(vmat[temp][i] && !visited[i]){				visited[i] = 1;				prev[i] = temp;				q[tail++] = i;			}	}	for(i = 0;i < n;i++)		if(!visited[i])			return -1;	return tail;}int main(){	cin >> n >> m;	towns = new town[n];	ditches = new ditch[m];	int i = 0;	for(i = 0;i < n;i++)		cin >> towns[i].name >> towns[i].x >> towns[i].y;	for(i = 0;i < m;i++)		cin >> ditches[i].x1 >> ditches[i].y1 >> ditches[i].x2 >> ditches[i].y2;	construct_matrix();	int x = buildSpanningTree();	if(x == -1){		cout << "NO";		return 0;	}	cout << "YES\n" << x-1 << "\n";	for(i = x-1;i > 0;i--)		cout << towns[q[i]].name << " " << towns[prev[q[i]]].name << "\n";	return 0;}