#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <iostream>
#include <vector>
#include <climits>
#include <cmath>
#include <time.h>    
#include <ctime>
#include <cstring>
#include <omp.h>

#define BUFFSIZE 200

struct myPair
{
	int x;
	int y;
	myPair** links;
	int linkSize;
	int linkCapacity;
	int idx;
	bool active;
};

struct myResult
{
	int x;
	int y;
	int idx;
};

#define MAX_PARTS 200
#define MAX_PART_SIZE 5500
//std::vector<myPair> data;
int totalParts;
int myPartSize[MAX_PARTS + 1];
myPair** myData[MAX_PARTS + 1];
std::vector<myResult> result;
std::vector<int> finalResult;
int finalScore = 0;

int myN = 0;
int R = 0;
int partSize = 0;

clock_t begin = clock();

void save(const char* fileName)
{
	FILE* out;
	out = fopen(fileName, "w");

	fprintf(out, "%ld\n", finalResult.size());

	for (size_t z = 0; z < finalResult.size(); z++)
	{
		fprintf(out, "%d ", finalResult[z]);
	}
	fclose(out);
}

inline static void AddLink(myPair* item, myPair* tmp) {
	item->linkSize++;
	if (item->linkCapacity <= item->linkSize) {
		if (item->linkCapacity == 0) item->linkCapacity = 1;
		else item->linkCapacity = item->linkCapacity * 2;
		item->links = (myPair**)realloc(item->links, sizeof(myPair*) * item->linkCapacity);
	}
	item->links[item->linkSize - 1] = tmp;
}


inline static void EraseLink(myPair* item, int idx) {
	myPair** links = item->links;
	item->linkSize--;
	links[idx] = links[item->linkSize];
}

void solve(int part, int N, int mode, bool reverse) {
	myPair** data = myData[part];
	//reverse
	if (reverse) {
		int half = N / 2;
		for (int z = 0; z < half; z++) {
			myPair* tmp = data[z];
			data[z] = data[N - z - 1];
			data[N - z - 1] = tmp;
		}
	}


	double R2 = (double)R * 2;
	R2 = R2 * R2;
	int R2i = (int)((float)R * 2);

	for (int i = 0; i < N; i++) {
		myPair* tmp = data[i];
		for (int k = i + 1; k < N; k++) {
			myPair* item = data[k];
			double dx = tmp->x - item->x;
			double dy = tmp->y - item->y;
			if (dx < 0) dx *= -1;
			if (dy < 0) dy *= -1;
			if (dx <= R2i && dy <= R2i)
			{
				if ((dx * dx + dy * dy) < R2)
				{
					AddLink(item, tmp);
					AddLink(tmp, item);
				}
			}
		}
		if (clock() - begin > 4000000) break;
	}
	int bestIdx = -1;
	do {		
		bestIdx = -1;
		int bestHits = INT_MAX;
		int bestTotalNear = INT_MAX;
		if (mode == 2) bestTotalNear = 0;
		if (mode == 3 || mode == 4) {
			bestHits = 0;
			bestTotalNear = 0;
		}
		for (int i = 0; i < N; i++) {
			myPair* tmp = data[i];
			if (tmp->active) {
				if (tmp->linkSize <= 0) {
					myResult mr;
					mr.idx = tmp->idx;
					mr.x = tmp->x;
					mr.y = tmp->y;
					result.push_back(mr);
					tmp->active = false;
					N--;
					data[i] = data[N];
					i--;
					continue;
				}

				if (mode == 5) {
					int totalNear = 0;
					for (int k = 0; k < tmp->linkSize; k++) {
						if (tmp->links[k]->active) totalNear += tmp->links[k]->linkSize;
					}
					if (totalNear < bestTotalNear) {
						bestTotalNear = totalNear;
						bestIdx = i;
					}
				}
				else if (mode == 4) {
					int totalNear = 0;
					for (int k = 0; k < tmp->linkSize; k++) {
						if (tmp->links[k]->active) totalNear += tmp->links[k]->linkSize;
					}
					if (totalNear > bestTotalNear) {
						bestTotalNear = totalNear;
						bestIdx = i;
					}						
				}
				else if (mode == 3) {
					if (tmp->linkSize > bestHits) {
						bestHits = tmp->linkSize;
						bestIdx = i;
						bestTotalNear = 0;
						for (int k = 0; k < tmp->linkSize; k++) {
							if (tmp->links[k]->active) bestTotalNear += tmp->links[k]->linkSize;
						}
					}
					else if (tmp->linkSize == bestHits) {
						int totalNear = 0;
						for (int k = 0; k < tmp->linkSize; k++) {
							if (tmp->links[k]->active) totalNear += tmp->links[k]->linkSize;
						}
						if (totalNear > bestTotalNear) {
							bestTotalNear = totalNear;
							bestIdx = i;
						}
					}
				}
				else {
					if (tmp->linkSize < bestHits) {
						bestHits = tmp->linkSize;
						bestIdx = i;
						bestTotalNear = 0;
						for (int k = 0; k < tmp->linkSize; k++) {
							if (tmp->links[k]->active) bestTotalNear += tmp->links[k]->linkSize;
						}
					}
					else if (mode == 0 && tmp->linkSize == bestHits) {
						int totalNear = 0;
						for (int k = 0; k < tmp->linkSize; k++) {
							if (tmp->links[k]->active) totalNear += tmp->links[k]->linkSize;
						}
						if (totalNear < bestTotalNear) {
							bestTotalNear = totalNear;
							bestIdx = i;
						}
					}
					else if (mode == 2 && tmp->linkSize == bestHits) {
						int totalNear = 0;
						for (int k = 0; k < tmp->linkSize; k++) {
							if (tmp->links[k]->active) totalNear += tmp->links[k]->linkSize;
						}
						if (totalNear > bestTotalNear) {
							bestTotalNear = totalNear;
							bestIdx = i;
						}			
					}
				}
			}
		}

		if (mode == 3) {
			if (bestIdx >= 0) {
				myPair* bestItem = data[bestIdx];
				//hit main circle
				bestItem->active = false;

				//update hits
				for (int j = 0; j < bestItem->linkSize; j++) {
					myPair* sublink = bestItem->links[j];
					if (sublink->active) {
						for (int m = 0; m < sublink->linkSize; m++) {
							if (sublink->links[m] == bestItem) {
								EraseLink(sublink, m);
								m--;
							}
						}
					}
				}

				N--;
				data[bestIdx] = data[N];
			}
		}
		else {
			if (bestIdx >= 0) {
				myPair* bestItem = data[bestIdx];
				myResult mr;
				mr.idx = bestItem->idx;
				mr.x = bestItem->x;
				mr.y = bestItem->y;
				result.push_back(mr);
				//hit main circle
				bestItem->active = false;

				//remove hits			
				for (int k = 0; k < bestItem->linkSize; k++) {
					myPair* tmp = bestItem->links[k];
					if (tmp->active)
					{
						tmp->active = false;
						//update hits
						for (int j = 0; j < tmp->linkSize; j++) {
							myPair* sublink = tmp->links[j];
							if (sublink->active) {
								for (int m = 0; m < sublink->linkSize; m++) {
									if (sublink->links[m] == tmp) {
										EraseLink(sublink, m);
										m--;
									}
								}
							}
						}
					}
				}
				N--;
				data[bestIdx] = data[N];
			}
		}
		if (clock() - begin > 4000000) break;
	} while (bestIdx != -1);

}

bool load(const char* fileName)
{
	char tempBuffer[BUFFSIZE];
	FILE* in;
	in = fopen(fileName, "r");
	if (in == NULL) return false;

	if (fgets(tempBuffer, BUFFSIZE, in))
	{
		sscanf(tempBuffer, "%d %d", &myN, &R);
	}
	result.clear();
	result.reserve(myN);
	//data.reserve(N);
	partSize = myN;
	if (partSize > MAX_PART_SIZE) {
		partSize = MAX_PART_SIZE;
	}

	totalParts = 0;
	int size = myN;
	int idx = 0;
	do {
		int currentPartSize = partSize;
		if (size < partSize) currentPartSize = size;
		myData[totalParts] = (myPair**)malloc(currentPartSize * sizeof(myPair*));
		myPartSize[totalParts] = currentPartSize;
		size -= currentPartSize;

		myPair** data = myData[totalParts];
		for (int i = 0; i < currentPartSize; i++) {
			idx++;
			myPair* tmp = new myPair();
			tmp->links = NULL;
			tmp->active = true;
			tmp->linkSize = 0;
			tmp->linkCapacity = 0;
			tmp->idx = idx;
			//tmp.links.reserve(R * R);
			fgets(tempBuffer, BUFFSIZE, in);
			sscanf(tempBuffer, "%d %d", &tmp->x, &tmp->y);
			data[i] = tmp;
		}
		totalParts++;
	} while (size > 0);

	fclose(in);
	return true;
}



void check() {
	int finalSize = result.size();
	int finalPart = totalParts;
	myPartSize[finalPart] = finalSize;
	totalParts++;
	myData[finalPart] = (myPair**)malloc(finalSize * sizeof(myPair*));
	myPair** data = myData[finalPart];
	for (int i = 0; i < finalSize; i++) {
		myResult r = result[i];
		myPair* tmp = new myPair();
		tmp->links = NULL;
		tmp->active = true;
		tmp->linkSize = 0;
		tmp->linkCapacity = 0;
		tmp->idx = r.idx;
		tmp->x = r.x;
		tmp->y = r.y;
		data[i] = tmp;
	}
	result.clear();
	solve(finalPart, finalSize, 0, false);
}

void check_fast() {
	double R2 = (double)R * 2;
	R2 = R2 * R2;
	int R2i = (int)((float)R * 2);
	for (int i = 0; i < result.size(); i++) {
		myResult* tmp = &result[i];
		if (tmp->idx == 0) continue;
		for (int k = i + 1; k < result.size(); k++) {
			myResult* item = &result[k];
			if (item->idx == 0) continue;
			double dx = tmp->x - item->x;
			double dy = tmp->y - item->y;
			if (dx < 0) dx *= -1;
			if (dy < 0) dy *= -1;
			if (dx <= R2i && dy <= R2i)
			{
				if ((dx * dx + dy * dy) < R2)
				{
					item->idx = 0;
				}
			}
		}
	}
}

int work(int mode, bool reverse)
{

	load("mars.in");
	#pragma omp parallel for 
	for (int z = 0; z < totalParts; z++) {
		solve(z, myPartSize[z], mode, reverse);
	}
	if (clock() - begin > 4000000) check_fast();
	else {
		if (result.size() < partSize) check();
		else check_fast();
	}
	int score = 0;
	for (size_t z = 0; z < result.size(); z++)
	{
		if (result[z].idx > 0) score++;
	}

	if (finalScore < score) {
		finalResult.clear();
		finalResult.reserve(score);
		for (size_t z = 0; z < result.size(); z++)
		{
			if (result[z].idx > 0) finalResult.push_back(result[z].idx);
		}
		finalScore = finalResult.size();
	}

	return score;
}

void freeit() {
	for (int i = 0; i < totalParts; i++) {
		myPair** data = myData[i];
		if (data != NULL) {
			int pSize = myPartSize[i];
			for (int k = 0; k < pSize; k++) {
				if (data[k]->links != NULL) {
					free(data[k]->links);
					data[k]->links = NULL;
				}
			}
			delete data;
		}
	}
	result.clear();
}

int main(int argc, char* argv[])
{
	bool order = true;

	work(2, order);

	if (clock() - begin < 2300000) {
		freeit();
		work(0, order);
	}

	if (clock() - begin < 2300000) {
		freeit();
		work(1, order);
	}

	if (clock() - begin < 2300000) {
		freeit();
		work(3, order);
	}

	if (clock() - begin < 2300000) {
		freeit();
		work(4, order);
	}

	if (clock() - begin < 2300000) {
		freeit();
		work(5, order);
	}



	order = false;
	if (clock() - begin < 2300000) {
		freeit();
		work(2, order);
	}

	if (clock() - begin < 2300000) {
		freeit();
		work(0, order);
	}

	if (clock() - begin < 2300000) {
		freeit();
		work(1, order);
	}

	if (clock() - begin < 2300000) {
		freeit();
		work(3, order);
	}

	if (clock() - begin < 2300000) {
		freeit();
		work(4, order);
	}

	if (clock() - begin < 2300000) {
		freeit();
		work(5, order);
	}



	save("mars.out");

	return 0;
}