> 不知道错在哪里了，本地测试都可以的，代码如下
> #include <stdio.h>
> #include <string.h>
> #define min(a,b)	((a)>(b)?(b):(a))
> #define max(a,b)	((a)>(b)?(a):(b))
> 
> int Len;
> int Map[11][11];
> int Max;
> int colorOk;
> int color[11];
> 
> typedef struct Point
> {
> 	int x,y;
> }Point;
> 
> typedef struct Line
> {
>        struct Point sp;     //线段起点
>        struct Point ep;     //线段终点       
>  }Line,*pLine;
> 
> 
> int IsIntersect(pLine L1,pLine L2)
> {
>   int x12,y12,x34,y34,x13,y13;  
> 
>   y12=L1->ep.y - L1->sp.y;
>   x12=L1->ep.x - L1->sp.x;
>   y34=L2->ep.y - L2->sp.y;
>   x34=L2->ep.x - L2->sp.x;
>   x13=L2->sp.x - L1->sp.x;
>   y13=L2->sp.y - L1->sp.y; 
> 
>  if(x34*y12==x12*y34){
> 	  if((x13*y34==y13*x34) && (x12*y13==y12*x13 ))
> 	    return 1;      //Line
> 	  else
> 		return 0;     //None
>   }
>   else
> 	  return 2;         //Intersection  
> }
> 
> 
> 
> int Cross(Line L1,Line L2) 
> { 
>     if(L1.sp.x == L2.ep.x && L1.sp.y == L2.ep.y
> 			&& L1.ep.x == L2.sp.x && L1.ep.y == L2.sp.y
> 		||L1.sp.x == L2.sp.x && L1.sp.y == L2.sp.y
> 			&& L1.ep.x == L2.ep.x && L1.ep.y == L2.ep.y)
> 		return 1;
> 	if(min(L2.sp.x,L2.ep.x)>=max(L1.sp.x,L1.ep.x)
>         ||max(L2.sp.x,L2.ep.x)<=min(L1.sp.x,L1.ep.x)
> 		||min(L2.sp.y,L2.ep.y)>=max(L1.sp.y,L1.ep.y)
> 		||max(L2.sp.y,L2.ep.y)<=min(L1.sp.y,L1.ep.y))
> 	    return 0;  //快速排斥实验    
> 
>    return IsIntersect(&L1,&L2);
> } //判断两条线段是否相交的函数   
> 
> int Add(char NameT[],char CountryName[][21],int L)
> {
> 	int i;
> 	int NeedCmp = 1;
> 	for(i=0;i<L;i++)
> 		if(strcmp(CountryName[i],NameT) == 0) 
> 		{
> 			NeedCmp = 0;
> 			break;
> 		}
> 	if(NeedCmp)	
> 	{
> 		strcpy(CountryName[i],NameT);
> 		Len++;
> 	}
> 	return i;
> }
> 
> 
> int ok(int vertexNumber)
> {
> 	int i;
> 	for(i=0;i<Len;i++)
> 		if(Map[vertexNumber][i]==1&&color[vertexNumber]==color[i])
> 			return 0;
>     return 1;
> }
> 
> void backTrack(int verNum,int verColorCount)
> {
> 	int i;
> 	if(verNum>Len)
> 	{
> 		colorOk=1;
> 	}
> 	else
> 	{
> 		for(i=1;i<=verColorCount;i++)
> 		{
> 			color[verNum-1]=i;
> 			if(ok(verNum-1) )
> 				backTrack(verNum+1,verColorCount);
> 		}
> 	}
> }
> 
> 
> 
> int GetMinColor(Line CountryLineSet[][101],
> 				int CountryLineNum[])
> {
> 	int i,j,m,n;
> 	Line L1,L2;
> 
> 	for(i=0;i<Len;i++)
> 		for(j=i+1;j<Len;j++)
> 		{
> 			for(m=0;m<CountryLineNum[i];m++)
> 			{
> 					L1 = CountryLineSet[i][m];
> 
> 				for(n=0;n<CountryLineNum[j];n++)
> 				{
> 					L2 = CountryLineSet[j][n];					
> 					int res = Cross(L1,L2) ;
> 					if(res == 1)	
> 					{
> 						Map[i][j] = Map[j][i] = 1;
> 						break;
> 					}
> 				}
> 			}
> 			
> 		}
> 
>   colorOk = 0;
>   int colorCount;
>   for(i=1;i<=Len;i++)
>   {
> 	  colorCount=i;
> 	  backTrack(1,i);    //依次试探颜色数
> 	  if(colorOk==1) 
> 	  {
> 		  break;
> 	  }
>   }
> 	return colorCount;
> }
> 
> int main()
> {
> 
> 	char NameT[21];
> 	char CountryName[10][21];
> 	Line CountryLineSet[10][101];
> 
> 	int i,k,n,x,y;
> 	int firstx,firsty;
> 	int firstread;
> 	int CountryLineNum[10],index;
> 	int ColorNum;
> 	Line L;
> 	Point P;
> 	while(1)
> 	{
> 		scanf("%d",&n);
> 		if(n == 0)	break;
> 		memset(CountryName,0,10*21*sizeof(char));
> 		memset(CountryLineSet,0,10*101*sizeof(Line));
> 		memset(CountryLineNum,0,10*sizeof(int));
> 		memset(Map,0,11*11*sizeof(int));
> 
> 		k = 0;
> 		Len = 0;
> 		for(i=0;i<n;i++)
> 		{
> 			scanf("%s",NameT);
> 			k = Add(NameT,CountryName,Len);
> 			firstread = 1;
> 			
> 			while(1)
> 			{
> 				scanf("%d",&P.x);
> 				if(P.x == -1 && !firstread)	
> 				{
> 					L.sp.x = firstx;
> 					L.sp.y = firsty;
> 					L.ep.x = x;
> 					L.ep.y = y;
> 					index = CountryLineNum[k];
> 					CountryLineSet[k][index] = L;
> 					CountryLineNum[k]++;
> 					break;
> 				}
> 				scanf("%d",&P.y);
> 				if(!firstread)
> 				{
> 					L.sp.x = x;
> 					L.sp.y = y;
> 					L.ep.x = P.x;
> 					L.ep.y = P.y;
> 					index = CountryLineNum[k];
> 					CountryLineSet[k][index] = L;
> 					CountryLineNum[k]++;
> 				}
> 				else
> 				{
> 					firstx = P.x;
> 					firsty = P.y;
> 				}
> 
> 				x = P.x;
> 				y = P.y;
> 				firstread = 0;
> 			}//while(1) break with -1
> 		
> 		}//read block
> 	   ColorNum = GetMinColor(CountryLineSet,CountryLineNum);
> 		printf("%d\n",ColorNum);
> 	}
> 
> 
> 	return 0;
> }
> 
> 测试数据如下:
> 6
> Blizid
> 0 0
> 60 0
> 60 60
> 0 60
> 0 50
> 50 50
> 50 10
> 0 10
> -1
> Blizid
> 0 10
> 10 10
> 10 50
> 0 50
> -1
> Windom
> 10 10
> 50 10
> 40 20
> 20 20
> 20 40
> 10 50
> -1
> Accent
> 50 10
> 50 50
> 35 50
> 35 25
> -1
> Pilot
> 35 25
> 35 50
> 10 50
> -1
> Blizid
> 20 20
> 40 20
> 20 40
> -1
> 4
> A1234567890123456789
> 0 0
> 0 100
> 100 100
> 100 0
> -1
> B1234567890123456789
> 100 100
> 100 200
> 200 200
> 200 100
> -1
> C1234567890123456789
> 0 100
> 100 100
> 100 200
> 0 200
> -1
> D123456789012345678
> 100 0
> 100 100
> 200 100
> 200 0
> -1
> 6
> A
> 0 0
> 1 0
> 1 1
> 0 1
> -1
> B
> 0 1
> 1 1
> 1 2
> 0 2
> -1
> C
> 1 1
> 2 1
> 2 2
> 1 2
> -1
> D
> 1 0
> 2 0
> 2 1
> 1 1
> -1
> A
> 1 2
> 2 2
> 2 3
> 1 3
> -1
> E
> 2 0
> 3 0
> 3 2
> 2 2
> -1
> 0

• Re:看错题 (127) springtty 2005-07-21 13:38:11