#include <stdio.h>#include <mpi.h>//進程號和處理器數目int my_rank,group_size;//第一個多邊形的端點double pointx1[20],pointy1[20];//第二個多邊形的端點double pointx2[20],pointy2[20];//多邊行的邊數int n_poly,m_poly;//判斷的結果int result,localresult;/* *函數名:if_not_parallel *功能:兩條直線不垂直的情況下,判斷是否相交 *輸入:(x1,y1),(x2,y2)是線段一的兩個端點的坐標 *     (x3,y3),(x4,y4)是線段二的兩個端點的坐標 *輸出:返回整型值判斷兩條線段是否相交 */int if_intersect_np(double x1,double y1,double x2,double y2, double x3,double y3,double x4,double y4){	double x;	x=((x1*y2-x2*y1)/(x2-x1)+(x4*y3-x3*y4)/(x4-x3))/((y2-y1)/(x2-x1)-(y4-y3)/(x4-x3));	if(((x1-x)*(x-x2)>=0)&&((x3-x)*(x-x4)>=0))	return 1;	else	return 0;}/* *函數名:if_intersect_1v *功能:線段一是垂直的,判斷線段二與一是否相交 *輸入:(x1,y1),(x2,y2)是線段一的兩個端點的坐標 *     (x3,y3),(x4,y4)是線段二的兩個端點的坐標 *輸出:返回整型值判斷兩條線段是否相交 */int if_intersect_1v(double x1,double y1,double x2,double y2, double x3,double y3,double x4,double y4){	double y;	if(x3==x4)		{		//兩線段平行，不在一條直線上		if(x3!=x1)			return 0;		else if((y4<y1)||(y2<y3))		return 0;		else		return 1;	}	//線段一垂直,線段二不垂直	else	{		//線段一所在直線與線段二所在直線的交點縱坐標		y = (y4 - y3)/(x4 - x3)*(x1 - x4)+ y4;		if((y>=y1)&&(y<=y2)&&(y<=y4)&&(y>=y3)&&((x4-x1)*(x3-x1)<=0))		return 1;		else		return 0;	}}/* *函數名:if_intersect *功能:判斷線段一(x1,y1),(x2,y2)與線段二(x3,y3),(x4,y4)是否相交 *輸入:(x1,y1),(x2,y2)是線段一的兩個端點的坐標 *     (x3,y3),(x4,y4)是線段二的兩個端點的坐標 *輸出:返回整型值判斷兩條線段是否相交 */int if_intersect(double x1,double y1,double x2,double y2, double x3,double y3,double x4,double y4){	double temp;	int result;	//將坐標大的換到第二個點	if(y1>y2)	{		temp = x1;		x1 = x2;		x2 = temp;		temp = y1;		y1 = y2;		y2 = temp;	}	if(y3>y4)	{		temp = x3;		x3 = x4;		x4 = temp;		temp = y3;		y3 = y4;		y4 = temp;	}	//線段一為垂直線段	if(x1==x2)		{		result=if_intersect_1v(x1,y1,x2,y2,x3,y3,x4,y4);	}		else	{		/*線段一不垂直，線段二垂直*/		if(x3==x4)		//交換線段一線段二位置，遞歸調用本函數判斷兩線段是否相交		result= if_intersect(x3,y3,x4,y4,x1,y1,x2,y2);		//線段一線段二皆不垂直		else		{			//若兩線段中存在平行于x軸的			if((y1==y2)||(y3==y4))			//交換線段一線段二中x,y位置，遞歸調用本函數判斷兩線段是否相交			result= if_intersect(y1,x1,y2,x2,y3,x3,y4,x4);			//線段一線段二平行			else if((y4-y3)*(x2-x1)==(x4-x3)*(y2-y1))			{				//兩線段所在直線在y軸上的截距相同，則兩線段在同一直線上				if((x4*y3-x3*y4)*(x2-x1)==(x2*y1-x1*y2)*(x4-x3))				{					//兩線段在一條直線上，但不相交					if((y4<y1)||(y2<y3))					result = 0;					//兩線段在一條直線上，且相交					else					result = 1;				}				//兩線段不在同一直線上				else				result = 0;			}			//兩線段不平行			else			{				result=if_intersect_np(x1,y1,x2,y2,x3,y3,x4,y4);			}		}	}	return result;}/* *函數名:Broadcast *功能:將兩個多邊形的數據傳到個處理器 *輸入:無 *輸出:無 */void Broadcast(){	MPI_Barrier(MPI_COMM_WORLD);	MPI_Bcast(&n_poly,1,MPI_INT,0,MPI_COMM_WORLD);	MPI_Bcast(&m_poly,1,MPI_INT,0,MPI_COMM_WORLD);	MPI_Bcast(pointx1,n_poly,MPI_DOUBLE,0,MPI_COMM_WORLD);	MPI_Bcast(pointy1,n_poly,MPI_DOUBLE,0,MPI_COMM_WORLD); 	MPI_Bcast(pointx2,m_poly,MPI_DOUBLE,0,MPI_COMM_WORLD);	MPI_Bcast(pointy2,m_poly,MPI_DOUBLE,0,MPI_COMM_WORLD);	MPI_Barrier(MPI_COMM_WORLD);}/* *函數名:Judge() *功能:判斷兩個多邊形是否相交 *輸入:無 *輸出:無 */void Judge(){	int i,j,k;	/*對第二個多邊形的每條邊，若還未發現兩多	邊形相交, 就判斷是否與第一個多邊形	的邊集相交, 對應于算法17.4步驟（3）	*/	result = 0;	localresult = 0;	for(i=0;(i<m_poly)&&(result==0);i++)	{		/*對處理器分配判斷的第一個多邊形的		邊集*/		for(j=0;j<n_poly/group_size+1;j++)		{		/*累加第二個多邊形當前邊與第一		個多邊形邊集相交的判斷結		果*/			if(j*group_size+my_rank<n_poly)			{				k=j*group_size+my_rank;				localresult+=if_intersect(pointx1[k],pointy1[k],pointx1[(k+1)%n_poly],pointy1[(k+1)%n_poly],pointx2[i],pointy2[i],pointx2[(i+1)%m_poly],pointy2[(i+1)%m_poly]);				}		}		/*統計第二個多邊形與第一個多邊形是		否相交, 對應于算法17.4步驟(4)*/		MPI_Scan(&localresult,&result,1,MPI_INT,MPI_SUM,MPI_COMM_WORLD);	}}/* *函數名:GetData *功能:取得多邊形的各種數據 *輸入:無 *輸出:無 */void GetData(){	int i;	//0號處理器	if(my_rank==0)	{		//輸入多邊形相關數據		printf("please input first polygon\n");		printf("please input the count of vertex:");		scanf("%d",&n_poly);		printf("please input the vertex\n");		for(i=0;i<n_poly;i++)		{			scanf("%lf",&pointx1[i]);			scanf("%lf",&pointy1[i]);		}		printf("please input second polygon\n");		printf("please input the count of vertex:");		scanf("%d",&m_poly);		printf("please input the vertex\n");		for(i=0;i<m_poly;i++)		{			scanf("%lf",&pointx2[i]);			scanf("%lf",&pointy2[i]);		}	}}/* *函數名:main *功能:判斷兩個多邊形是否相交 *輸入:argc為命令行參數個數 *     argv為每個命令行參數組成的字符串數組。 *輸出：返回0代表程序正常結束 */int main(int argc,char * argv[]){	    /*完成任務1:初始化*/   	MPI_Init(&argc,&argv);	MPI_Comm_rank(MPI_COMM_WORLD,&my_rank);	MPI_Comm_size(MPI_COMM_WORLD,&group_size);	/*完成任務2:從輸入中獲取數據*/    GetData();	/*完成任務3:將數據廣播到每個處理器*/	Broadcast();	/*完成任務4:判斷是否相交*/    Judge();    /*完成任務5:輸出結果*/	MPI_Barrier(MPI_COMM_WORLD);	if(my_rank==0)	{		if(result!=0)		printf("two polygons intersect\n");		else		printf("two polygons don't intersect\n");	}	MPI_Finalize();}