INFOMAN брой 18

/*
 Задача 4: Векторна сума
 При правоъгълна координатна система Oxy в равнината е дадена точка A и съв-
 купност от N < 20 ненулеви вектори. Точката A не съвпада с началото на коорд-
 инатната система. Напишете програма за съставяне на сума в която да участват
 някои от дадените вектори, евентуално и повече от веднъж, но не повече от 5
 пъти, така че ако постравим началото на получената векторна сума в началото
 на координатната система, краят и да съвпадне с A.
 Решение:
 Предложеното решение е рекурсивно. Ясно е, че подобен подход е верен, но
 прекалено бавен, затова ще приложим някои оптимизации.
 1. Векторната сума ще се разраства само в рамките на квадранта на точка А.
 Ясно е, че това не премахва решения, а просто ограничава последователността,
 в която векторите се добавят. Така ако без ограничение приемем, че точката е
 в първи квадрант, на първата стъпка няма да можем да включваме вектори с
 отрицателни координати, а на всяка следваща, те ще са ограничени до осите
 на координатната система, но ще могат да достигат самата точка А.
 2. Сортираме векторите по ортогоналната им проекция на графиката на правата
 минаваща през O( 0, 0 ) и A, като (ако А е отново в първи квадрант,)
 по-големите стойности са по-напред. Намирането на тази права,
 X * x + Y * y = 0 (X, Y - const и графиката минава през О - затова няма
 свободен член) става чрез следната матрица:
     ( X   Y  1 )
 M = (a.x a.y 1 )
     ( 0   0  1 )
 За да бъдат точките О и А на правата определена по-горе, трябва d(M) = 0
 <=> X * a.x + Y * a.y = 0
 По намерените по този начин X и Y, можем да намерим и
 Y * vector[i].x - X * vector[i].y, за всяко i, по което да сортираме точките.
 Това не променя по никакъв начин броя на генерираните векторни суми, а само
 последователността, в която се пораждат.
 Ясно е, че тази оптимизация би била много по-пълноценна ако можехме да огра-
 ничим сумите и отгоре, но аз не можах да измисля никаква реална горна граница.
*/

#include <stdio.h>
#include <stdlib.h>

#define MAX 20

typedef struct { long x, y; } VECTOR;

#define abs( x ) ( x < 0 ? -1 : x > 0 )

VECTOR a = { 5000, 5000 }; // точката А
VECTOR vector[] = {{ -1000, -1000 }, { 1000, 1000 }};  // входните вектори
VECTOR pos;  // текущата сума
int n = 2;
int count[MAX];  // брой повтаряния на всеки вектор в текущата сума

int cmpfn( void *x1, void *x2 )  // помощна функция за qsort()
{
  VECTOR v1, v2;

  v1 = *(VECTOR*)x1;
  v2 = *(VECTOR*)x2;

  return ( v2.y - v1.y ) * a.x - ( v2.x - v1.x ) * a.y;
}

add( int curr )
{
  long i, j;

  if(( !a.x || !( i = vector[curr].x + pos.x ) || abs( a.x ) == abs( i ) )
   &&( !a.y || !( j = vector[curr].y + pos.y ) || abs( a.y ) == abs( j ) ))
  {
    pos.x = i, pos.y = j,
    count[curr]++;
    if( pos.x == a.x && pos.y == a.y )
    {
      for( i = j = 0; i < n; i++ )
        if( count[i] ) j++;
      printf( "%d", j );
      for( i = 0; i < n; i++ )
        if( count[i] )
          printf( "\n%.f %.f %d",
             (float)vector[i].x / 1000, (float)vector[i].y / 1000, count[i] );
      exit( 0 );
    }
    for( i = 0; i < n; i++ )
      if( count[i] < 5 ) add( i );
    pos.x -= vector[curr].x, pos.y -= vector[curr].y,
    count[curr]--;
  }
}

main()
{
  int i;

  qsort( vector, n, sizeof( VECTOR ), cmpfn );

  for( i = 0; i < n; i++ )
    add( i );

  printf( "0" );
}