1004.cpp

第33届ACM亚洲区域赛（哈尔滨赛区预选）1004题目源码

#include<stdio.h>
#include<math.h>
/*
   Graham_scan(Point PointSet[],Point ch[],int n,int &len);

参数：
PointSet[]：输入的点集
ch[]：输出的凸包上的点集，按照逆时针方向排列
n：PointSet中的点的数目
len：输出的凸包上的点的个数
 
返回值：
 null
*/
typedef struct Point{
    double x,y;
}; 
double multiply(Point p1,Point p2,Point p0)
{
    return((p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y)); 
}

double distance(Point p1,Point p2)
{
    return(sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y))); 
}

void Graham_scan(Point PointSet[],Point ch[],int n,int &len)
{
    int i,j,k=0,top=2;
    Point tmp;

   for(i=1;i<n;i++)
    if ((PointSet[i].y<PointSet[k].y)||((PointSet[i].y==PointSet[k].y)&&(PointSet[i].x<PointSet[k].x)))
    k=i;
    tmp=PointSet[0];
    PointSet[0]=PointSet[k];
    PointSet[k]=tmp; 
    for (i=1;i<n-1;i++)
        {
        k=i;
        for (j=i+1;j<n;j++)
            if ( (multiply(PointSet[j],PointSet[k],PointSet[0])>0) ||
                     ((multiply(PointSet[j],PointSet[k],PointSet[0])==0)
                         &&(distance(PointSet[0],PointSet[j]) < distance(PointSet[0],PointSet[k]) ) ) )
                k=j;
        tmp=PointSet[i];
        PointSet[i]=PointSet[k];
        PointSet[k]=tmp;
        }
    ch[0]=PointSet[0];
    ch[1]=PointSet[1];
    ch[2]=PointSet[2]; 
    for (i=3;i<n;i++)
        {
        while (multiply(PointSet[i],ch[top],ch[top-1])>=0) top--;
        ch[++top]=PointSet[i];
        }
    len=top+1;
}
double alld(Point p, int n, Point a[]){
	int i;
	double sum = 0;
	for(i = 0; i < n; i++){
		sum += distance(p, a[i]);
	}
	return sum;
}
Point pin[101], pout[101];
int main(){
	int t, n, i, len, flag;
	double step, nx, ny, sx, sy, alllen, oldlen;
	char s[101];
	Point tmpp;
	gets(s);
	sscanf(s, "%d", &t);
	while(t--){
		gets(s);
		gets(s);
		sscanf(s, "%d", &n);
		for(i = 0; i < n; i++){
			gets(s);
			sscanf(s, "%lf %lf", &pin[i].x, &pin[i].y);
		}
		Graham_scan(pin, pout, n, len);
		step = 100;
		nx = pout[0].x;
		ny = pout[0].y;
		tmpp.x = nx;
		tmpp.y = ny - step;
		oldlen = alld(tmpp, len, pout);
		while(step > 0.2){
			flag = 1;
			while(flag){
				flag = 0;
				tmpp.x = nx;
				tmpp.y = ny - step;
				alllen = alld(tmpp, len, pout);
				if(alllen < oldlen){
					sx = tmpp.x;
					sy = tmpp.y;
					oldlen = alllen;
					flag = 1;
				}
				tmpp.x = nx;
				tmpp.y = ny + step;
				alllen = alld(tmpp, len, pout);
				if(alllen < oldlen){
					sx = tmpp.x;
					sy = tmpp.y;
					oldlen = alllen;
					flag = 1;
				}
				tmpp.x = nx - step;
				tmpp.y = ny;
				alllen = alld(tmpp, len, pout);
				if(alllen < oldlen){
					sx = tmpp.x;
					sy = tmpp.y;
					oldlen = alllen;
					flag = 1;
				}
				tmpp.x = nx + step;
				tmpp.y = ny;
				alllen = alld(tmpp, len, pout);
				if(alllen < oldlen){
					sx = tmpp.x;
					sy = tmpp.y;
					oldlen = alllen;
					flag = 1;
				}
				nx = sx;
				ny = sy;
			}
			step /= 2;
		}
		if(t){
			printf("%0.0lf\n\n", oldlen);
		}else{
			printf("%0.0lf\n", oldlen);
		}
		
	}
}