Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
1.8 kB
2
Indexable
#include <iostream>
#include <fstream>
using namespace std;

int k, r;
int m;
int n;
int ansNH[25];
int visited[25];
int Max;
int visitedNH[105];

typedef struct NH {
	int x, y;
};

typedef struct KH {
	int x, y, s;
};

typedef struct Point {
	int x, y;
};

NH arrNH[25];
KH arrKN[105];

bool check(Point P1, Point P2) {
	if (((P1.x - P2.x) * (P1.x - P2.x) + (P1.y - P2.y) * (P1.y - P2.y)) <= r * r)
		return true;
	return false;
}

void reset() {
	for (int i = 1; i <= n; i++) {
		visited[i] = 0;
	}
}

void BackTrack(int nh, int dem) {

	if (dem == k+1 && nh <= m+1) {
		reset();
		int sum = 0;
		for (int i = 1; i < dem; i++) {
			for (int j = 1; j <= n; j++) {

				Point nh;
				nh.x = arrNH[ansNH[i]].x;
				nh.y = arrNH[ansNH[i]].y;

				Point kn;
				kn.x = arrKN[j].x;
				kn.y = arrKN[j].y;

				if (check(nh, kn) && visited[j] == 0) {
					visited[j] = 1;
					sum += arrKN[j].s;
				}

			}
		}
		Max = max(Max, sum);
		return;
	}

	if (nh > m + 1)
		return;


	for (int c = 0; c <= 1; c++) {

		if (c == 0) {
			BackTrack(nh + 1, dem);
		}

		if (c == 1) {
			if (visitedNH[nh] == 0) {
				visitedNH[nh] = 1;
				ansNH[dem] = nh;
				BackTrack(nh + 1, dem + 1);
				visitedNH[nh] = 0;
			}
		}

	}
}

int main() {
	ifstream input("input.txt");
	fstream output;
	output.open("output.txt");
	int t;
	input >> t;
	for (int tc = 1; tc <= t; tc++) {
		input >> k >> r;
		input >> m;
		for (int i = 1; i <= m; i++) {
			input >> arrNH[i].x >> arrNH[i].y;
			visitedNH[i] = 0;
		}

		input >> n;
		for (int i = 1; i <= n; i++) {
			input >> arrKN[i].x >> arrKN[i].y >> arrKN[i].s;
		}

		Max = -1;
		BackTrack(1, 1);
		output << "#" << tc << " ";
		output << Max << endl;
	}
}