Първо Kонтролно за BOI 2004, Задача 2. ТОЧКИ
Уловието на задачата може да прочетете тук.
Решение
За решаването на задачата ще използваме следната зависимост между лицето
на многоъгълника и броят на точките с целочислени координати (наричани просто
точки за в бъдеще) по контура и във вътрешност му. Ако означим лицето на
многоъгълника с A, броят на точките по контура с B, броят на
точките във вътрешността с I, то имаме следната зависимост.
A = 1/2 B + I - 1
Има лесни алгоритми, с които може да намерим броят на точките по контура на
многоъгълника, както и неговото лице. Веднъж намерили ги може да изразим броят
на точките във вътрешността и така да решим задачата.
Лицето на многоъгълника ще намерим използвайки алгоритъм със сложност
O(N), който работи като сумира следното произведение (xj -
xj+1) * (yj + yj+1) за всяко j = 1, 2,
..., N (N+1 е еквивалентно на 1). Сумата която образувахме
взета по абсолютна стойност е равна на удвоеното лице на многоъгълника.
Намирането на точките по контура ще извършим като намерим точките върху всяка
страна и прибавим N (точите по ъглите на многоъгълника). Броят на точките
върху една отсечка е равен на най-големия общ делител на разликите в x и
y координатите на двете точки, краища на отсечката минус едно. Тоест
имаме сумата на gcd(|xj-xj|,
|yj-yj|) - 1, за всяко j = 1, 2, ..., N
(N+1 е еквивалентно на 1). В горната формула с gcd сме
означили функцията за намиране на най-голям общ делител.
Примерна реализация
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 1001;
struct Point
{
int x, y;
};
int n;
Point ps[maxn];
void solve();
int main()
{
solve();
return 0;
}
void solve()
{
int i, a2, b;
int area2();
int border();
scanf("%d", &n);
for (i = 0; i < n; i++)
scanf("%d%d", &ps[i].x, &ps[i].y);
ps[n] = ps[0];
a2 = area2();
b = border();
i = (a2 - b + 2) / 2;
printf("%d\n", b + i);
}
int area2()
{
int i, a;
for (i = a = 0; i < n; i++)
a += (ps[i].x - ps[i+1].x) * (ps[i].y + ps[i+1].y);
return abs(a);
}
int gcd(int a, int b)
{
int t;
while (b)
{
t = b;
b = a % b;
a = t;
}
return a;
}
int border()
{
int i, b;
for (i = b = 0; i < n; i++)
b += gcd(abs(ps[i].x - ps[i+1].x), abs(ps[i].y - ps[i+1].y));
return b;
}
Автор: Иван Анев
обратно към брой 27
|