2014
03-13

# Diamonds

Formally, a diamond with radius r, centered at (x,y), is the set of points whose manhattan distance to (x,y) is no more than r. Given n points p1, p2, …, pn on the plane, your task is to draw n diamonds, so that pi lies in the interior or on the border of the i-th diamond, and each diamond, except the first one, encloses the previous

The first line contains a single integer T (T <= 40), the number of test cases. Each case begins with a single integers n (1 <= n <= 200), the number of diamonds. Each of the following n lines contains three integers x, y, r (1 <= x, y <= 100000, 1 <= r <= 10000), indicating that the i-th diamond should cover (x,y), with radius r.

The first line contains a single integer T (T <= 40), the number of test cases. Each case begins with a single integers n (1 <= n <= 200), the number of diamonds. Each of the following n lines contains three integers x, y, r (1 <= x, y <= 100000, 1 <= r <= 10000), indicating that the i-th diamond should cover (x,y), with radius r.

2
1
1 1 1
2
1 1 1
4 1 2

Case 1:
1 1
Case 2:
1 1
2 1

#include <stdio.h>
#include <string.h>
struct node{
int x,y,r;
}e[300];
struct ppp{
int x,y;
} now[300][2],ans[300];

ppp trans(int x,int y)
{
ppp p;
p.x=x-y;
p.y=x+y;
return p;
}

ppp transs(int x,int y)
{
ppp p;
p.x=(x+y)/2;
p.y=(y-x)/2;
return p;
}

int mins(int x,int y)
{
return x<y?x:y;
}

int maxs(int x,int y)
{
return x>y?x:y;
}

ppp solve(int num)
{
int x,y,r;

for(int i=0;i<=num;i++)
{
x=e[i].x;
y=e[i].y;
r=e[num].r;
now[i][0]=trans(x-r,y);
now[i][1]=trans(x+r,y);
}
x=ans[num+1].x;
y=ans[num+1].y;
r=e[num+1].r-e[num].r;
//printf("r=%d\n",r);
now[num+1][0]=trans(x-r,y);
now[num+1][1]=trans(x+r,y);
//for(int i=0;i<=num+1;i++)
// printf("(%d %d)-(%d %d)\n",now[i][0].x,now[i][0].y,now[i][1].x,now[i][1].y);
//printf("num=%d\n",num) ;
for(int i=1;i<=num+1;i++)
{
now[0][0].x=maxs(now[0][0].x,now[i][0].x);
now[0][0].y=maxs(now[0][0].y,now[i][0].y);
now[0][1].x=mins(now[0][1].x,now[i][1].x);
now[0][1].y=mins(now[0][1].y,now[i][1].y);
}
//printf("ans=(%d %d)-(%d %d)\n",now[0][0].x,now[0][0].y,now[0][1].x,now[0][1].y);
/*for(int i=now[0][0].x;i<=now[0][1].x;i++)
{
for(int j=now[0][0].y;j<=now[0][1].y;j++) printf("(%d %d) ",i,j);printf("\n");
}*/
if ((now[0][0].x+now[0][0].y)%2==0) return transs(now[0][0].x,now[0][0].y);
if (now[0][0].x<now[0][1].x) return transs(now[0][0].x+1,now[0][0].y);
return transs(now[0][0].x,now[0][0].y+1);
}

int main()
{
int cas,n;

//freopen("in.txt","r",stdin);
scanf("%d",&cas);
for(int ll=1;ll<=cas;ll++)
{
scanf("%d",&n);
for(int i=0;i<n;i++) scanf("%d %d %d",&e[i].x,&e[i].y,&e[i].r);
ans[n].x=e[n-1].x;
ans[n].y=e[n-1].y;
e[n].r=e[n-1].r*2;
//ans[n].r*=2;
for(int i=n-1;i>=0;i--)
{
ans[i]=solve(i);
}
printf("Case %d:\n",ll);
for(int i=0;i<n;i++) printf("%d %d\n",ans[i].x,ans[i].y);
}
}

1. 这道题目虽然简单，但是小编做的很到位，应该会给很多人启发吧！对于面试当中不给开辟额外空间的问题不是绝对的，实际上至少是允许少数变量存在的。之前遇到相似的问题也是恍然大悟，今天看到小编这篇文章相见恨晚。