Принцип решения.

[MAKEDON]

У меня тут возник вопрос по поводу одной задачи. Ее нужно решать с помощью математических расчетов? Или моделировать ситуацию и смотреть результат? Но, тут проблема с размером массива.

Вот, собственно, задача:

[LeBron]

Можно решать математически, но это довольно геморный способ (имею ввиду решение, у которого сложность даже ниже, чем log(n), близко к О(1)), а сдесь прокатит и обычное моделирование в одном измерении (считать за О(1) целую линию в вертикальном или горизонтальном направлении), тогда получим О(N) относительно ширины области покрытия.

[Carbon]

Ради интереса решил. У меня получилась логарифмическая сложность.
ЗЫ Никакого массива не использовал.

[MAKEDON]

Чтобы решать в общем виде массивом нужно создать массив a[200000][200000]. Но это слишком большой, как быть?

[Carbon]

Кинуть своё решение?

[LeBron]

Если надо за линейное время (не самый оптимальный, но, как мне показалось, самый простой способ решения) - тогда линейный массив.
Если чуть пошевелить мозгами, то в таком случае можно и вообще без массива, ведь мы будем на ходу суммировать результаты с текущим ответом.

[Carbon]

Ладно. Мой вариант:

#include <stdio.h>


inline bool in_round( int x, int y, int x3, int y3, int r )
{
	return ( x - x3 )*( x - x3 ) + ( y - y3 )*( y - y3 ) <= r*r;
}


long long count( int xs, int ys, int xf, int yf, int x3, int y3, int r )
{
	bool ss = in_round( xs, ys, x3, y3, r );
	bool sf = in_round( xs, yf, x3, y3, r );
	bool fs = in_round( xf, ys, x3, y3, r );
	bool ff = in_round( xf, yf, x3, y3, r );

	if ( ss && sf && fs && ff ) return ( long long )( xf - xs + 1 )*( long long )( yf - ys + 1 );
	if ( !ss && !sf && !fs && !ff ) return 0;
	
	if ( xs < xf && ys == yf )
	{
		int xm = ( xs + xf )/2;
		return count( xs, ys, xm, yf, x3, y3, r ) + count( xm + 1, ys, xf, yf, x3, y3, r );
	}

	if ( xs == xf && ys < yf )
	{
		int ym = ( ys + yf )/2;
		return count( xs, ys, xf, ym, x3, y3, r ) + count( xs, ym + 1, xf, yf, x3, y3, r );
	}

	if ( xs < xf && ys < yf )
	{
		int xm = ( xs + xf )/2;
		int ym = ( ys + yf )/2;

		return count( xs, ys, xm, ym, x3, y3, r ) + count( xm + 1, ys, xf, ym, x3, y3, r ) +
			count( xs, ym + 1, xm, yf, x3, y3, r ) + count( xm + 1, ym + 1, xf, yf, x3, y3, r );
	}

	return 0;
}


int main( int, char ** )
{

	int x1, y1;
	int x2, y2;
	int x3, y3;
	int r;

	scanf( "%d%d%d%d%d%d%d", &x1, &y1, &x2, &y2, &x3, &y3, &r );

#define min( a, b ) ( ( a ) < ( b ) ? ( a ) : ( b ) )
#define max( a, b ) ( ( a ) > ( b ) ? ( a ) : ( b ) )

	int xs = max( x1, x3 - r ), ys = max( y1, y3 - r );
	int xf = min( x2, x3 + r ), yf = min( y2, y3 + r );
	int x = min( xs, x3 );
	int y = min( ys, y3 );

	printf( "count = %I64u", count( xs - x, ys - y, xf - x, yf - y, x3 - x, y3 - y, r ) );

	getchar();
	getchar();

	return 0;
}