Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

100题目纪念

Posted by 274856653 at 2019-06-14 15:45:25 on Problem 1127
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <ctype.h>
#define MAX_N 13+5
#define MAX_INT 0x3f3f3f3f 
typedef struct
{
		int x; 
		int y;
}Point;
typedef struct
{
		Point A; 
		Point B; 
}Line;
typedef struct
{
		int x1; 
		int y1; 
		int x2; 
		int y2;
}LineT;

//struct LineT { int x1; int y1; int x2; int y2; };

int n = 0;

Line stLine[MAX_N];

int iMaxix[MAX_N][MAX_N];


void initVar()
{
		int i, j;
		memset((char *)&stLine, 0, sizeof(stLine));
		for(i = 0; i<n; i++)
		{
				for(j = 0; j<n; j++)
				{
						if(i == j)
								iMaxix[i][j] = 0;
						else
								iMaxix[i][j] = MAX_INT;
				}
		}
}

void printfMatrix()
{
		int i, j;
		for(i = 0; i<n; i++)
		{
				for(j = 0; j<n; j++)
				{
						printf("%12d", iMaxix[i][j]);
				}
				printf("\n");
		}
}

int crossProduct(Point P0, Point P1, Point P2)
{
		int iTemp = (P1.x - P0.x)* (P2.y -P0.y) - (P2.x- P0.x) *(P1.y - P0.y);

		//printf("iTemp is %d\n", iTemp);
		return iTemp; 
}

int max(int a, int b)
{
		if(a>b)
				return a;
		else
				return b;
}
int min(int a, int b)
{
		if(a<b)
				return a;
		else
				return b;
}
int IsLineCross(Line H, Line K)
{
		if( max(H.A.x, H.B.x)< min(K.A.x, K.B.x) ||
			max(H.A.y, H.B.y)< min(K.A.y, K.B.y) ||		
		    max(K.A.x, K.B.x)< min(H.A.x, H.B.x) ||
			max(K.A.y, K.B.y)< min(H.A.y, H.B.y) )
		{
//				printf("coordinate is out of band\n");
				return 0;
		}
		if(crossProduct(H.A, K.A, H.B) * crossProduct(H.A, K.B, H.B) >0 ||	
		   crossProduct(K.A, H.A, K.B) * crossProduct(K.A, H.B, K.B) >0)
		{
//				printf("coordinate crossProduct is bigger than zero\n");
				return 0;
		}

//		printf("coordinate is meet requirement cross\n");
		return 1;

}
void IsTwoLineCross()
{
		int i, j;
		LineT l1, l2;

		for(i = 0; i<n; i++)
		{
				for(j = i; j<n; j++)
				{
						if(i == j)
								continue;

						//printf("i = %d, j = %d\n", i, j);

						l1.x1= stLine[i].A.x;
						l1.y1= stLine[i].A.y;
						l1.x2= stLine[i].B.x;
						l1.y2= stLine[i].B.y;
						l2.x1= stLine[j].A.x;
						l2.y1= stLine[j].A.y;
						l2.x2= stLine[j].B.x;
						l2.y2= stLine[j].B.y;

						//intersection(l1, l2);
						if(1 == IsLineCross(stLine[i],stLine[j]) )
						{
								iMaxix[i][j] = 0;
								iMaxix[j][i] = 0;
						}
				}
		}
}

void floyd()
{
		int i, j , k;

		for(k = 0; k<n; k++)
				for(i = 0; i<n; i++)
				{
						for(j = i; j<n; j++)
						{
								if(i == j)
										continue;
								if(iMaxix[i][j] == MAX_INT && iMaxix[i][k] == 0 && iMaxix[k][j] == 0)
								{
										iMaxix[i][j] = 0;
										iMaxix[j][i] = 0;
								}
										
						}
				}
}



int intersection( LineT l1,  LineT l2)
{       //快速排斥实验 
		if ((l1.x1 > l1.x2 ? l1.x1 : l1.x2) < (l2.x1 < l2.x2 ? l2.x1 : l2.x2) || 
		    (l1.y1 > l1.y2 ? l1.y1 : l1.y2) < (l2.y1 < l2.y2 ? l2.y1 : l2.y2) || 
			(l2.x1 > l2.x2 ? l2.x1 : l2.x2) < (l1.x1 < l1.x2 ? l1.x1 : l1.x2) || 
			(l2.y1 > l2.y2 ? l2.y1 : l2.y2) < (l1.y1 < l1.y2 ? l1.y1 : l1.y2)) 
		    { 
					printf("TT coordinate is out of band\n");
					return 0;
		   	} 
		//跨立实验 
		if ((((l1.x1 - l2.x1)*(l2.y2 - l2.y1) - (l1.y1 - l2.y1)*(l2.x2 - l2.x1))* ((l1.x2 - l2.x1)*(l2.y2 - l2.y1) - (l1.y2 - l2.y1)*(l2.x2 - l2.x1))) > 0 || 
		    (((l2.x1 - l1.x1)*(l1.y2 - l1.y1) - (l2.y1 - l1.y1)*(l1.x2 - l1.x1))* ((l2.x2 - l1.x1)*(l1.y2 - l1.y1) - (l2.y2 - l1.y1)*(l1.x2 - l1.x1))) > 0)
		{ 
				printf("TT coordinate crossProduct is bigger than zero\n");
				return 0; 
		} 
		printf("TT coordinate is meet requirement cross\n");
		return 1; 
}

int main()
{

		int i, j;
		int line1, line2 ;
		while(scanf("%d", &n))
		{
				//printf("n = %d\n", n);
				if(0 == n)
						break;

				initVar();
				for(i = 0; i<n; i++)
				{
						scanf("%d %d %d %d", &stLine[i].A.x, &stLine[i].A.y, &stLine[i].B.x, &stLine[i].B.y);
				//		printf("i = %d, stLine[i].A.x = %d, stLine[i].A.y = %d, stLine[i].B.x = %d, stLine[i].B.y = %d\n",i,  stLine[i].A.x, stLine[i].A.y, stLine[i].B.x, stLine[i].B.y);
				}
				//printf("before IsTwoLineCross \n");
				//printfMatrix();
				
				IsTwoLineCross();

				//printf("after IsTwoLineCross \n");
				//printfMatrix();

				floyd();

				//printf("after floyd \n\n\n");
				//printfMatrix();

				while(scanf("%d %d", &line1, &line2))
				{
				//printf("line1 is %d, line2 is %d\n", line1, line2);
				if( 0 == line1 && 0 == line2)
						break;
				
				if(0 == iMaxix[line1-1][line2-1])
						printf("CONNECTED\n");
				else
						printf("NOT CONNECTED\n");
				}

		}
		return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator