Из заданного множества точек на плоскости выбрать две различные точки так, что-бы окружности заданного радиуса с центрами в этих точках содержали внутри себя одинаковое количество точек.
Алгоритм:
1.Создаем две функции для генерации и записи точек в файл и считывания точек из файла.
2.Создаем функцию для нахождения расстояния между двумя точками.
3.Считываем значение всех координат точек из файла в массив.
4.Высчитываем для каждой точки количество точек, которые покрывает окружность радиуса R с центром в текущей точке и заносим значение в отдельный массив.
5. Находим в этом массиве два одинаковых значения.
#include <graphics.h>
#include <math.h>
#include <stdlib.h>
#include <stdio.h>
#include <conio.h>
#define N 100// макрос
#define R 50// макрос
void createPoints();// прототип функции
void readPoints();// прототип функции
int covered[N];// массив для хранения количества точек
/*структура в которой будем хранить точки*/
struct point{
int x, y;
}p[N];// массив структур в который считываем точки
/*функция для нахождения расстояния между двумя точками применение т.Пифагора*/
int dist(const point &a, const point &b) {
double x = a.x - b.x;
double y = a.y - b.y;
return (int) sqrt((double) x * x + y * y);
}
int main(){
/*инициализация графики*/
int gdriver = DETECT, gmode, errorcode;
initgraph(&gdriver, &gmode, "e:\\borlandc\\bgi");
int i, j;
createPoints();
readPoints();
/*рисуем каждую точку на экране как две окружности с разными радиусами*/
setcolor(YELLOW);
for (i = 0; i < N; i++)
{
int x = p[i].x;
int y = p[i].y;
circle(x, y,1);
circle(x, y,2);
}
/*для каждой точки высчитываем количество точек, которые покрывают окружность радиуса R с центром в текущей точке*/
for(i = 0; i < N; i++)
{
int cnt = 0;
for(int j = 0; j < N; j++)
{
if(i!=j)// не учитываем что точка покрывает саму себя
{
if(dist(p[i],p[j])<=R)
cnt++;
}
}
covered[i] = cnt;
}
/*перебираем все пары точек, если в текущей паре количество точек покрываемой первой и второй одинаково то ответ найден!рисуем окружности*/
int ok = 0;
for(i = 0; ok == 0 && i < N; i++)
for(j = i + 1; ok == 0 && j < N; j++)
if(covered[i] == covered[j])
{
ok = 1;
setcolor(GREEN);
circle(p[i].x, p[i].y, R);
circle(p[j].x, p[j].y, R);
}
getch();
return 0;
}
/*функция генерирует точки и записывает их в файл points.dat*/
void createPoints() {
FILE *f = fopen("e:\\temp\\points.dat", "w");
srand( time(0));
for (int i = 0; i < 100; i++)
fprintf(f, "%d %d\n", R + (rand() % (getmaxx() - 2 * R)),
R + (rand() % (getmaxy() - 2 * R)));
fclose(f);
}
/*функция считывает точки из файла и заносит их в массив*/
void readPoints() {
FILE *f = fopen("e:\\temp\\points.dat", "r");
for (int i = 0; i <100; i++)
fscanf(f, "%d%d", &p[i].x, &p[i].y);
fclose(f);
}
Ключевые слова:
окружность, множество точек, расстояние, массив, файл
