Как найти количество параллелограмма

CPP

Java

Python3

C#

Javascript

Входные данные

В первой строке находится целое число n (1 ≤ n ≤ 2000) — количество точек.

В следующих n строках находятся пары целых чисел (x_i, y_i) (0 ≤ x_i, y_i ≤ 10⁹) — координаты i-й точки.

Выходные данные

Выведите одно целое число c — количество параллелограммов с вершинами в заданных точках.

Пример

4
0 1
1 0
1 1
2 0

Я должен решить проблему, когда, учитывая размер сетки N x M, я должен найти количество параллелограммов, которые «могут быть помещены в него» таким образом, чтобы каждая их координата была целым числом.

Вот мой код:

/*
~Keep It Simple!~
*/

#include<fstream>

#define MaxN 2005

int N,M;
long long Paras[MaxN][MaxN]; // Number of parallelograms of Height i and Width j
long long Rects; // Final Number of Parallelograms

int cmmdc(int a,int b)
{
while(b)
{
int aux = b;
b = a -(( a/b ) * b);
a = aux;
}

return a;
}

int main()
{
freopen("paralelograme.in","r",stdin);
freopen("paralelograme.out","w",stdout);

scanf("%d%d",&N,&M);

for(int i=2; i<=N+1; i++)
for(int j=2; j<=M+1; j++)
{
if(!Paras[i][j])
Paras[i][j] = Paras[j][i] = 1LL*(i-2)*(j-2) + i*j - cmmdc(i-1,j-1) -2; // number of parallelograms with all edges on the grid + number of parallelograms with only 2 edges on the grid.
Rects += 1LL*(M-j+2)*(N-i+2) * Paras[j][i]; // each parallelogram can be moved in (M-j+2)(N-i+2) places.
}

printf("%lld", Rects);
}

Пример: для сетки 2×2 у нас есть 22 возможных параллелограмма.

Мой алгоритм работает, и он правильный, но мне нужно сделать его немного быстрее. Я хочу знать, как это возможно.

Постскриптум Я слышал, что я должен предварительно обработать наибольший общий делитель и сохранить его в массиве, который сократит время выполнения до O (n * m), но я не уверен, как это сделать без использования cmmdc ( наибольший общий делитель) функция.

1

Убедитесь, что N не меньше, чем M:

if( N < M ){ swap( N, M ); }

Используйте симметрию в своих циклах, вам нужно всего лишь запустить j от 2 до i:

for(int j=2; j<=min( i, M+1); j++)

вам не нужен дополнительный массив Paras, брось это. Вместо этого используйте временную переменную.

long long temparas = 1LL*(i-2)*(j-2) + i*j - cmmdc(i-1,j-1) -2;
long long t1 = temparas * (M-j+2)*(N-i+2);
Rects += t1;
// check if the inverse case i <-> j must be considered
if( i != j && i <= M+1 ) // j <= N+1 is always true because of j <= i <= N+1
Rects += t1;

Заменить эту строку: b = a -(( a/b ) * b); используя оператор остатка:

b = a % b;

Возможно, было бы возможно кэширование результатов cmmdc. Вы можете инициализировать массив с помощью алгоритма сортировки: создайте двумерный массив, индексированный с помощью a и b, поставьте «2» в каждой позиции, где a и b кратны 2, а затем поставьте « 3 «в каждой позиции, где a и b кратны 3, и так далее, примерно так:

int gcd_cache[N][N];

void init_cache(){
for (int u = 1; u < N; ++u){
for (int i = u; i < N; i+=u ) for (int k = u; k < N ; k+=u ){
gcd_cache[i][k] = u;
}
}
}

Не уверен, что это сильно поможет.

0

Первый комментарий в вашем коде гласит: «будь проще», поэтому, в свете этого, почему бы не попытаться решить проблему математически и распечатать результат.

Если вы выберете две линии длины N из вашей сетки, вы найдете количество параллелограммов следующим образом:

• Выберите две точки рядом друг с другом в обеих строках: есть (N-1)^2
  способы сделать это, так как вы можете расположить две точки на N-1
  позиции на каждой из линий.
• Выберите две точки с одним пробелом между ними в обеих линиях: есть (N-2)^2 способы сделать это.
• Выберите две точки с двумя, тремя и до N-2 пробелы между ними.
• Итоговое количество комбинаций будет (N-1)^2+(N-2)^2+(N-3)^2+...+1,
• Решив сумму, мы получим формулу: 1/6*N*(2*N^2-3*N+1), Проверьте Вольфрам Альфа проверять.

Теперь, когда у вас есть решение для двух строк, вам просто нужно умножить его на число комбинации порядка 2 М, который является M!/(2*(M-2)!),

Таким образом, вся формула будет: 1/12*N*(2*N^2-3*N+1)*M!/(M-2)!, где ! знак обозначает факториал, и ^ обозначает оператор степени (обратите внимание, что тот же знак не является оператором степени в C ++, но побитовый XOR оператор).

Этот расчет требует меньше операций, чем итерация по матрице.

0