不知道错在哪里了，本地测试都可以的，代码如下
#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

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