dog.c

PASCAL光盘资料PASCAL光盘资料PASCAL光盘资料

/*
 Izborne pripreme 2002. - 2. izborni ispit - 2. zadatak - PAS
 Rjesenje napisao: Davor Bonaci <[e-mail]>
*/

#include <stdio.h>
#include <limits.h>

#define MAX 100001

long x[MAX], y[MAX], d[MAX], xr[MAX], yr[MAX], pl[MAX], mi[MAX];
long i, j, n, plus, minus;
FILE *inn, *out;

int main(void)
{
 inn = fopen("dog.in", "rt");
 out = fopen("dog.out", "wt");
 fscanf(inn, "%ld", &n);
 mi[0] = LONG_MAX;
 for (i=1;i<=n;i++)
 {
   fscanf(inn, "%ld%ld%ld", &x[i], &y[i], &d[i]);
   pl[i] = pl[i-1];

   if (x[i]+y[i] > pl[i])
     pl[i] = x[i] + y[i];

   mi[i] = mi[i-1];

   if (x[i]-y[i] < mi[i])
     mi[i] = x[i] - y[i];
 }
 fclose(inn);

 xr[n+1] = x[n];
 yr[n+1] = y[n]-d[n];
 d[n+1] = d[n];

 for (i=n;i>=1;i--)
 {
   xr[i] = xr[i+1];
   yr[i] = yr[i+1] - d[i+1] + d[i];

   for (j=i;j<=i;j++)
   {
     if (xr[i] + yr[i] < pl[j] - d[j])
       plus = pl[j]-d[j];
     else
       plus = xr[i]+yr[i];

     if (xr[i] - yr[i] > mi[j] + d[j])
       minus = mi[j] + d[j];
     else
       minus = xr[i]-yr[i];

     xr[i] = (plus + minus) / 2;
     yr[i] = (plus - minus + 1) / 2;
   }
 }

 for (i=1;i<=n;i++)
   fprintf(out,"%ld %ld\n", xr[i], yr[i]);
 fclose(out); return 0;
}