jam's store(2005年浙江大学编程竞赛，问题1004）

来源：百度知道 编辑：UC知道 时间：2024/05/29 03:44:02
Zhejiang University Programming Contest 2005
ZyXEL Cup

April 16th, 2005, Contest Session

Problem 1004: Jam’s Store
Time Limit: 2 second
________________________________________
Jam has a very large store full of valuable gems. The store is so large that Jam has hired many guards to watch the store. Each guard stays at a fixed position. But recently, Jam found out that there were still some gems stolen. So he decided to rearrange all his guards such that the minimum distance between those guards is maximized. The strategy is to ask each guard to go up or down one unit distance. That is, a guard at position (x, y) may be rearranged to (x, y+1) or (x, y-1).
How, it is not an easy task. So Jam is asking you for help. It is given that initially all the guards are not staying at the same row, that is, for each two guards at (x1, y1) and (x2, y2), y1 is not equal to y2.
Input:
The input contains multiple test cases. For each test case

#include<iostream>
#include<cmath>
struct Point
{
int x,y;
};
int calDis(Point a,Point b)
{
return (a.x-b.x)*(a.x-b.x)
+(a.y-b.y)*(a.y-b.y);
}
int main()
{
Point p[200];
int dis[200][200];
int n,i,j,x,y;
int maxDis,minDis;
bool used[200];
while(scanf("%d",&n)!=EOF)
{
if(n==0) break;
for(i=0;i<n;++i)
{
scanf("%d%d",&(p[i].x),&(p[i].y));
p[i].x--; p[i].y--;
}
for(i=0;i<n;++i)
for(j=i+1;j<n;++j)
dis[j][i]=dis[i][j]=calDis(p[i],p[j]);
std::fill_n(used,n,false);
maxDis=0;
while(true)
{
minDis=60000000;
for(i=0;i<n;++i)
for(j=i+1;j<n;++j)
if(dis[i][j]<minDis)
{
minDis=dis[i][j];
x=i; y=j;
}
if(minDis>maxDis)
maxDis=minDis;