Брой 26 на Списание Инфоман
 


Първо 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;
}

			

Автор: Иван Анев


обратно към брой 26