#include <stdio.h>

typedef struct Point
{
  double x,y;
}Point,*pPoint;

struct Point P[1000000];


struct Point GetM(struct Point *p1,
		   struct Point *p2,
		   struct Point *p3)
{
	struct Point D;
	D.x = (p1->x+p2->x+p3->x)/3;
	D.y = (p1->y+p2->y+p3->y)/3;
	return D;
}


int main()
{
	int TestCase;
	int n;
	int i,j;
	struct Point BP;
//	FILE *fp;
//	fp = fopen("Fin.txt","r");

	scanf("%d",&TestCase);
	while(TestCase)
	{
		scanf("%d",&n);
		for(i=0;i<n;++i)			
			scanf("%lf%lf",&P[i].x,&P[i].y);
		if(n%2 == 1)
		{
			j = 0;
		    while(j < n-4)
			{
				BP = P[0];
				for(i=1;i<=n-j-2;i++)
					P[i-1] = GetM(&BP,&P[i],&P[i+1]);
				j++;
			}
			BP = GetM(&P[0],&P[1],&P[2]);
			printf("%.2f %.2f\n",BP.x,BP.y);
		}
		else
		{
			j = 0;
		    while(j < n-3)
			{
				BP = P[0];
				for(i=1;i<=n-j-2;i++)
					P[i-1] = GetM(&BP,&P[i],&P[i+1]);
				j++;
			}

			printf("%.2f %.2f\n",(P[0].x+P[1].x)/2,(P[0].y+P[1].y)/2);
		}
		TestCase--;
	}
	
//	fclose(fp);
	return 0;
}

• 你这个复杂度是多少的? (1186) xfxyjwf 2005-07-23 13:07:49