http://acm.pku.edu.cn/JudgeOnline/problem?id=1054
Пример решения на 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.
Пример решения на С++:
Код:
#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; }