Рішення задачі «Цілочисельні точки»

Для рішення цієї задачі потрібно використати формулу Піка, яка виглядає таким чином:

x = s - n div 2 + 1, де s – площа багатокутника, n – кількість цілочисельних точок на його сторонах.

Тобто, нам необхідно знати площу багатокутника. Нам відома формула S = 1/2 * |Σ_i=1ⁿ[OP_i, OP_i+1]|, або перетворення її і рахуючи координати точки O за (0; 0), отримуєм S = 1/2 * |(x₁y₂ - x₂y₁) + (x₂y₃ - x₃y₂) + ... + (x_ny₁ - x₁y_n)|. Користуючись даною формулою і послідовно зчитуючи координати (потрібно не забувати про остатнього члена даної суми – зберегти координати першої точки), легко отримати площу – спочатку знайти суму всіх членів послідовності, пізніше взяти модуль і поділити на 2 (незабувши, що результат дійсне число).

На цьому ж кроці потрібно підрахувати кількість точок із цілочисельними координатами на сторонах багатокутника. Для цього потрібно підрахувати довжину проекцій кожної сторони на координатні осі. Кількість точок на стороні  - НСД довжин проекцій кожної сторони на координатні осі. НСД обчислюється за алгоритмом Евкліда. На кожному кроці заміняють більше з двох чисел на стачу від ділення (різницю від віднімання) більшого числа на менше, до цих пір поки одне із чисел не стане рівний нулю. Число, яке залишилось не рівне нулю буде найбільшим спільним дільником. При підрахунку точок слідує не забувати порахувати відрізок, який з’єднує остатню і першу точки багатокутника.

Тепер ми підрахували всі необхідні компоненти і осталось використати формулу Піка:  

x = s - n div 2 + 1.

program zadach_3;

  var

     a:array[1..1000,1..2] of longint;

     f,t:text;

     i,n:integer;

     s,dx,dy,ns,k:longint;

  procedure nsd (x,y:longint; var s:longint);

             begin

                if x=0 then s:=y

                           else

                               if y=0 then s:=x

                                          else

                                             begin

                                               while x<>y do

                                                   if x>y then x:=x-y

                                                              else y:=y-x;

                                                s:=x;

                                              end;

                end;

 begin

   assign(f,'input08.txt');

   reset (f);

   Readln(f,n);

   k:=0;

   readln(f,a[1,1],a[1,2]);

   for i:=2 to n do

     begin

       readln(f,a[i,1],a[i,2]);

       s:=s+(a[i-1,1]*a[i,2]-a[i,1]*a[i-1,2]);

       dx:=abs(a[i,1]-a[i-1,1]);

       dy:=abs(a[i,2]-a[i-1,2]);

        nsd(dx,dy,ns);

       k:=k+ns;

     end;

  close(f);

  s:=s+(a[n,1]*a[1,2]-a[1,1]*a[n,2]);

   dx:=abs(a[1,1]-a[n,1]);

   dy:=abs(a[1,2]-a[n,2]);

   nsd(dx,dy,ns);

   k:=k+ns;

   s:=round(abs(s)/2);

   s:=s-k div 2 +1;

   assign(t,'e.out');

   rewrite(t);

   writeln(t,s);

   close(t);

   end.

Перших п’ять тестів оцінюються по 10 балів.

6,7 – 15 балів.(вихід за тип Longint);

8 – 20 балів (1000 точок).