---

   Входные данные

   Выходные данные

   Пример входных данных

   Пример выходных данных

   Анализ условия и обсуждение идеи решения

   Пример решения на Pascal:

program PKU1054;
{$R-,S-,I-,Q-}

const
  inf = '';
  ouf = '';
  maxn = 5000;

var f: array[1 .. maxn, 1 .. maxn] of boolean;
    x, y: array[1 .. maxn] of longint;
    buf: array[0 .. 1 shl 18] of byte;
    ans, h, w, n: longint;

var midx, midy: longint;
    temp: longint;

procedure sort(l, r: longint);
var i, j: longint;
begin
  i := l; midx := x[(l * 2 + r) div 3];
  j := r; midy := y[(l * 2 + r) div 3];
  while i <= j do begin
    while (x[i] < midx) or (x[i] = midx) and (y[i] < midy) do i := i + 1;
    while (x[j] > midx) or (x[j] = midx) and (y[j] > midy) do j := j - 1;
    if i <= j then begin
      temp := x[i]; x[i] := x[j]; x[j] := temp;
      temp := y[i]; y[i] := y[j]; y[j] := temp;
      i := i + 1; j := j - 1;
    end;
  end;
  if i < r then sort(i, r);
  if l < j then sort(l, j);
end;

procedure prepare;
var i: longint;
begin
  assign(input, inf);
  settextbuf(input, buf);
  reset(input);
  readln(h, w);
  readln(n);
  for i := 1 to n do begin
    readln(x[i], y[i]);
    f[x[i], y[i]] := true;
  end;
  close(input);
end;

procedure main;
var i, j, p, q, x0, y0, now: longint;
begin
  ans := 0;
  for i := 1 to n - 1 do
    for j := i + 1 to n do begin
      p := x[j] - x[i];
      q := y[j] - y[i];
      if (p = 0) and (q = 0) then continue;
      x0 := x[i] - p; y0 := y[i] - q;
      if (x0 > 0) and (x0 <= h) and (y0 > 0) and (y0 <= w) then continue;
      x0 := x[j]; y0 := y[j];
      now := 2;
      while true do begin
        x0 := x0 + p; y0 := y0 + q;
        if x0 > h then break;
        if x0 < 1 then break;
        if y0 > w then break;
        if y0 < 1 then break;
        if not f[x0, y0] then begin
          now := 0;
          break;
        end;
        now := now + 1;
      end;
      if now > ans then ans := now;
    end;
  if ans < 3 then ans := 0;
end;

procedure print;
begin
  assign(output, ouf); rewrite(output);
  writeln(ans);
  close(output);
end;

begin
  prepare;
  sort(1, n);
  main;
  print;
end.

Пример решения на C++: 

#include "stdio.h"
#include "stdlib.h"

struct PLANT
{
       int x, y;
}plant[5001];
 
int row, col, n;
 
int cmp(const void *a, const void *b)
{
       PLANT *x = (PLANT *)a, *y = (PLANT *)b;
       if(x -> x == y -> x)    return x -> y - y -> y;
       return x -> x - y -> x;
}
 
void input()
{
       int i;
       scanf("%d %d", &row, &col);
       scanf("%d", &n);
       for(i=0; i<n; i++)
              scanf("%d %d", &plant[i].x, &plant[i].y);
}
 
int solve();
 
int main()
{
       input();
       qsort(plant, n, sizeof(PLANT), cmp);
       int temp = solve();
       if(temp > 2)                               
              printf("%d\n", temp);
       else
              printf("0\n");
       return 0;
}
 
int solve()
{
    int max = 0, temp;
    int i, j;
    PLANT n1, n2, jump, next;
    
    for(i=0; i < n; i++)
    {
        for(j=i+1; j < n; j++)
        {
            temp = 2;
            n1 = plant[i];
            n2 = plant[j];
            jump.x = plant[j].x - plant[i].x;
            jump.y = plant[j].y - plant[i].y;
            if(n1.x - jump.x > 0 && (n1.y - jump.y > 0 && n1.y - jump.y <= col) )
                continue;
            if(n1.x + max*jump.x > row || n1.y + max*jump.y > col || n1.y + max*jump.y <= 0)
                continue;
            next.x = plant[j].x + jump.x;
            next.y = plant[j].y + jump.y;
            while(next.x <= row && next.y <= col && next.x > 0 && next.y > 0)
            {
                PLANT * a = (PLANT *) bsearch( &next, plant, n, sizeof(PLANT), cmp);
               
                if(a == NULL)
                {
                    temp = 0;
                    break;
                }
                temp ++;           
                next.x += jump.x;
                next.y += jump.y;
            }
            if(temp > max)    max = temp;
        }
    }    
    return max;
}

Попередня

Зміст

Наступна