Jest zadanie (z kolokwium z lat ubiegłych): Mamy dany zbiór punktów. type punkt=record x:integer; y:integer; end; tab=array[1..max] of punkt; Napisz funkcję, która zwróci najmniejszą odległość między środkami ciężkości 2 niepustych podzbiorów tego zbioru. Ktoś może napisał to zadania i ma kod? Albo ma jakiś pomysł jak to rozwiązać?

lowest_distance.cpp

/*
Mamy dany zbiór punktów.
type
punkt=record
x:integer;
y:integer;
end;
tab=array[1..max] of punkt;
Napisz funkcję, która zwróci najmniejszą odległość między środkami ciężkości 2 niepustych podzbiorów
tego zbioru.
*/
#include<cstdio>
#include<algorithm> //min,max
#include<cmath> //sqrt

#define MAX 2
#define INF 2e9

using namespace std;

struct point
{
  int x,y;
};

int sq(int a) {
  return a*a;
}

int lowest_distance(point tab[], int n, int sumx1, int sumy1, int l1, int sumx2, int sumy2, int l2) {
  if(n==0 and l1 > 0 and l2 > 0) {
    int dx = sumx1/l1 - sumx2/l2;
    int dy = sumy1/l1 - sumy2/l2;
    return sq(dx)+sq(dy);
  } else if(n ==0 and (l1 == 0 or l2 == 0)) return 2e9;
  return min(lowest_distance(tab,n-1,sumx1+tab[n-1].x,sumy1+tab[n-1].y,l1+1,sumx2,sumy2,l2),
    min(lowest_distance(tab,n-1,sumx1,sumy1,l1,sumx2+tab[n-1].x,sumy2+tab[n-1].y,l2+1),
      lowest_distance(tab,n-1,sumx1,sumy1,l1,sumx2,sumy2,l2)
      )
    );
}

int main() {
  point tab[MAX];
  point tmp;
  tmp.x=1; tmp.y=1;
  tab[0] = tmp;
  tmp.x=-1; tmp.y=-1;
  tab[1] = tmp;
  //funkcja zwraca kwadrat odleglosci
  printf("%lf\n",sqrt(lowest_distance(tab,MAX,0,0,0,0,0,0)));

  return 0;
}