Зафарбовані клітинки

На аркуші паперу в клітинку накреслили ламану лінію з N вершин, які лежать на перетинах ліній сітки. Всі клітинки, які перетнула ламана, зафарбували (клітинка вважається перетнутою, якщо вона має з ламаною хоча б одну спільну точку). Обчислити кількість зафарбованих клітинок, якщо початок системи координат лежить на перетині ліній сітки, осі паралельні лініям сітки, а одиничний відрізок дорівнює стороні клітинки.

Вхідні дані

В першому рядку міститься натуральне число N - кількість вершин ламаної. У наступних N рядках - по два цілих числа, розділених пропусками, координати кожної з вершин ламаної. Всі числа по модулю не перевищують 100.

Вихідні дані

Вивести кількість перетнутих клітинок.

• Ліміт часу 1 секунда
• Ліміт використання пам'яті 64 MiB

Вхідні дані

3

2 3

-2 0

1 -2

Вихідні дані

18

Розв'язання

Наочним обладнанням до задачі може бути старенький монітор з малою роздільною здатністю, наприклад 320*240, - це майже як у дисплея сучасного телефону. Тепер декілька зауважень безпосередньо щодо розв'язування задачі.

• координати N вершин ламаної читаємо в масив координат Т;
• інформацію про "перетнутість" клітинок зберігатимемо в матриці С, де C[i,j] кількість можливих перетинів комірки, що має вершини (i,j), (i+1, j), (i, j+1), (i+1, j+1) з ланками ламаної;
• для кожної ланки з кінцями в точках T[k], T[k+1] переглядаємо всі клітинки, які можуть бути "перетнутими" цією ланкою;
• у випадку, якщо всі вершини клітинки лежать по один бік від відповідної ланки, то клітинка не перетинається ламаною;
• після перегляду всіх ланок кількість ненульових елементів у матриці С буде відповіддю до задачі.

var
N:integer;
T:array [1..mm] of Tpset;
C:array [-mm..mm,-mm..mm] of integer;
Mx, Lx, My, Ly, CC:integer;
procedure Init;
var
i,j:integer;
f:text;
begin
assign(f, fi);
reset(f);
for i:=-mm to mm do
   for j:=-mm to mm do
C[i,j]:=0;
Mx:=-777;
Lx:=777;
My:=-777;
Ly:=777;
readln(f,N);
for i:=1 to N do const mm=100;
Fi='input.txt';
Fo='output.txt';
type
Tpset=record
X,Y:integer;
end;
begin
readln(f, T[i].X, T[i].Y);
if T[i].X>Mx then Mx:=T[i].X;
if T[i].X<Lx then Lx:=T[i].X;
if T[i].Y>My then My:=T[i].Y;
if T[i].Y<Ly then Ly:=T[i].Y;
end;
close(f);
end;
function zz (u:integer):integer;
begin
if u>0 then zz:=1;
if u<0 then zz:=-1;
if u=0 then zz:=0;
end;
function Cell (A,B:Tpset; x,y:integer):boolean;
var z1, z2, z3, z4:integer;
begin
z1:=ZZ((x - A.X)*(B.Y - A.Y) - (y - A.Y)*(B.X - A.X));
z2:=ZZ((x + 1 - A.X)*(B.Y - A.Y) - (y - A.Y)*(B.X - A.X));
z3:=ZZ((x - A.X)*(B.Y - A.Y) - (y + 1 - A.Y)*(B.X - A.X));
z4:=ZZ((x + 1 - A.X)*(B.Y - A.Y) - (y + 1 -A.Y)*(B.X - A.X));
Cell:=not (Abs(z1+z2+z3+z4)=4;
end;
procedure Run;
var
i,j,k:integer;
L,R,D,U:integer;
begin
for k:=1 to N-1 do
   begin
   if T[k].X<T[k+1].X then
      begin
      L:=T[k].X
      R:=T[k+1].X
      end;
   else
      begin
      L:=T[k+1].X;
      R:=T[k].X
      end;
if T[k].Y<T[k+1].Y then
   begin
   D:=T[k].Y;
   U:=T[k+1].Y
   end;
else
   begin
   D:=T[k+1].Y;
   U:=T[k].Y;
   end;
for i:=L - 1 to R do
   for j:=D - 1 to U do
      if Cell(T[k], T[k+1], i, j) then inc (C[i,j]);
end;
CC:=0;
for i:=Lx - 1 to Mx do
   for j:=Ly - 1 to My do
      if C[i,j]>0 then inc(CC);
end;
procedure Done;
var f:text;
begin
assign(f,Fo);
rewrite(f);
writeln(f,CC);
close(f);
end;
begin
init;
run;
done;
end.