задачка попалась, не пойм у условия не полные?

@dzrkot · Регистрация: 11.09.2013

Задача:
Даны два множества точек на плоскости. Найти радиус и центр окружности, проходящей через n(n>=3) точек первого множества и содержащей строго внутри себя равное число точек первого и второго множества.

помогаю тут одному товарисчу, естественно условия он и сам до конца не знает, так вот, сложилось ощущение, что задача в такой постановке решение имеет через раз, т.е. нету условий, которым должны удовлетворять эти множества, ни кол-во точек...

по идее что надо сделать - сгенерировать точки(ясное дело...), потом в цикле искать точку, которая будет равноудалена от хотя бы от 3 точек 1ого подмножества, а дальше проверять и считать точки внутри окружности, но как-то что-то мне здесь не нравится...

Не по теме:

есть хочу ппц :(((

@SatanaXIII · 20.12.2013, 11:09

Даны два множества точек на плоскости. Найти радиус и центр окружности, проходящей через n(n>=3) точек первого множества и содержащей строго внутри себя равное число точек первого и второго множества.

задачка попалась, не пойм у условия не полные?

Два множества точек: черные кружочки и фиолетовые крестики (если вдруг у кого монохромные дисплеи).
Допустим первое множество это черные точки.
Вводится n - количество точек, которые должны быть внутри окружности (в данном случае (на рисунке) три).
Каким-то образом перебираются окружности - этот алгоритм вам и нужно придумать. В данном случае тройками перебираются все точки первого множества и строится по ним окружность.
Будем считать (нужно уточнить), что точки, лежащие на самой окружности, принадлежат этой окружности, точнее удовлетворяют нашему условию.
Окружность номер 1 содержит в себе три точки первого множества, но только одну второго. Она не подходит, так как должно быть поровну. Не обязательно n (три)!
Окружность номер 2 содержит в себе четыре точки из первого множества, но только две из второго. Она не подходит.
Окружность номер 3 содержит три точки из первого множества и три точки из второго. Она и является исходной. (По условию задачи не понятно надо ли продолжать поиски далее, но скорее всего надо остановиться на первой нашедшейся)
В найденной окружности ищем центр и радиус.

@dzrkot · 20.12.2013, 16:25 **[ТС]**

Ну да, примерно так я и думал, но спасибо, так намного нагляднее задачка

Добавлено через 5 часов 6 минут
дико решил не без извращений
мб кому потом пригодится когди-нибудь

очень лень её доводить до ума, но условия выполяет

C++

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <cmath>
using namespace std;
 
bool dozor(double x, double y,double x0,double y0,double r)
{
if (sqrt(pow(abs(x-x0),2)+pow(abs(y-y0),2))<=r)
return true;
 
else
return false;
}
 
int main()
{
srand(time(0));
const int size=20;
double x[size];
double y[size];
double xx[size];
double yy[size];
 
int sizeFindEnd;
int sizeFindStart;
cout<<"Please enter range find:\nstart:";
cin>>sizeFindStart;
cout<<"end:";
cin>>sizeFindEnd;
    for (int i=0;i<size;i++)
    {
    x[i]=0+rand()%15;
    y[i]=0+rand()%15;
    xx[i]=0+rand()%15;
    yy[i]=0+rand()%15;
    }
cout<<"x:";
    for (int i=0;i<size;i++)
    cout<<x[i]<<" ";
 
cout<<"\ny:";
    for (int i=0;i<size;i++)
    cout<<y[i]<<" ";
cout<<endl;
for (int i=0;i<size;i++)
    for (int j=i;j<size;j++)
        for (int l=j;l<size;l++)
            for (double y0=0;y0<=sizeFindEnd;y0++)
                for (double x0=0;x0<=sizeFindEnd;x0++)
if (
 ((pow(abs(x[i]-x0),2)+pow(abs(y[i]-y0),2))==(pow(abs(x[j]-x0),2)+pow(abs(y[j]-y0),2)))&&
 ((pow(abs(x[j]-x0),2)+pow(abs(y[j]-y0),2))==(pow(abs(x[l]-x0),2)+pow(abs(y[l]-y0),2)))&&
 (x[i]!=x[l])&&(x[l]!=x[j])&&(x[i]!=x[j])
    )
 
{
    double r=sqrt(pow(abs(x[l]-x0),2)+pow(abs(y[l]-y0),2));
    cout<<"\n\nThis around may bee created:";
    cout<<"\nx0 = "<<x0<<"    y0 = "<<y0<<endl;
    cout<<"Radius : "<<r<<endl;
    cout<<"x1: "<<x[i]<<"   y1:"<<y[i]<<"           r^2 for 1:"<<(pow(abs(x[i]-x0),2)+pow(abs(y[i]-y0),2))<<endl;
    cout<<"x2: "<<x[j]<<"   y2:"<<y[j]<<"           r^2 for 2:"<<(pow(abs(x[j]-x0),2)+pow(abs(y[j]-y0),2))<<endl;
    cout<<"x3: "<<x[l]<<"   y3:"<<y[l]<<"           r^2 for 3:"<<(pow(abs(x[l]-x0),2)+pow(abs(y[l]-y0),2))<<endl;
    int counter1=0;
    int counter2=0;
        for (int z=0;z<size;z++)
    if (dozor(x[z],y[z],x0,y0,r))
        counter1++;
        for (int z=0;z<size;z++)
    if (dozor(xx[z],yy[z],x0,y0,r))
        counter2++;
 
    if (counter1==counter2)
        {
        char ready='0';
        cout<<"\n\nThis around have :"<<counter1<<" elments of array\n";
        cout<<"Do you wont see array? y/n:";
        cin>>ready;
            if (ready=='y')
            {
                cout<<"x:";
                for (int i=0;i<size;i++)
                cout<<x[i]<<" ";
                cout<<"\ny:";
                for (int i=0;i<size;i++)
                cout<<y[i]<<" ";
                cout<<"\n\nx2:";
                for (int i=0;i<size;i++)
                cout<<xx[i]<<" ";
                cout<<"\ny2:";
                for (int i=0;i<size;i++)
                cout<<yy[i]<<" ";
            cin.get();
            }
        }
}
 
return 0;
}

@dzrkot · 21.12.2013, 19:40 **[ТС]**

Не по теме:

ох, не стоила благодарности))

@dzrkot zzzZZZ... 527 / 358 / 94 Регистрация: 11.09.2013 Сообщений: 2,040
		1
	задачка попалась, не пойм у условия не полные? 20.12.2013, 10:28. Показов 476. Ответов 3 Метки нет (Все метки) Задача: Даны два множества точек на плоскости. Найти радиус и центр окружности, проходящей через n(n>=3) точек первого множества и содержащей строго внутри себя равное число точек первого и второго множества. помогаю тут одному товарисчу, естественно условия он и сам до конца не знает, так вот, сложилось ощущение, что задача в такой постановке решение имеет через раз, т.е. нету условий, которым должны удовлетворять эти множества, ни кол-во точек... по идее что надо сделать - сгенерировать точки(ясное дело...), потом в цикле искать точку, которая будет равноудалена от хотя бы от 3 точек 1ого подмножества, а дальше проверять и считать точки внутри окружности, но как-то что-то мне здесь не нравится... Не по теме: есть хочу ппц :((( 0

@SatanaXIII Почетный модератор 5845 / 2855 / 390 Регистрация: 01.11.2011 Сообщений: 6,903
	20.12.2013, 11:09	2
	Даны два множества точек на плоскости. Найти радиус и центр окружности, проходящей через n(n>=3) точек первого множества и содержащей строго внутри себя равное число точек первого и второго множества. Два множества точек: черные кружочки и фиолетовые крестики (если вдруг у кого монохромные дисплеи). Допустим первое множество это черные точки. Вводится n - количество точек, которые должны быть внутри окружности (в данном случае (на рисунке) три). Каким-то образом перебираются окружности - этот алгоритм вам и нужно придумать. В данном случае тройками перебираются все точки первого множества и строится по ним окружность. Будем считать (нужно уточнить), что точки, лежащие на самой окружности, принадлежат этой окружности, точнее удовлетворяют нашему условию. Окружность номер 1 содержит в себе три точки первого множества, но только одну второго. Она не подходит, так как должно быть поровну. Не обязательно n (три)! Окружность номер 2 содержит в себе четыре точки из первого множества, но только две из второго. Она не подходит. Окружность номер 3 содержит три точки из первого множества и три точки из второго. Она и является исходной. (По условию задачи не понятно надо ли продолжать поиски далее, но скорее всего надо остановиться на первой нашедшейся) В найденной окружности ищем центр и радиус. 1

@dzrkot
	21.12.2013, 19:40 [ТС] задачка попалась, не пойм у условия не полные? #4
	Не по теме: ох, не стоила благодарности)) 0

Опции темы