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

@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++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#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 **[ТС]**

Не по теме:

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

Новые блоги и статьи Все статьи Все блоги /
Звёздная пыль kumehtar 20.06.2025 Я просто это себе представляю: как создавался этот мир. Как энергия слипалась в маленькие частички. Как они собирались в первые звёзды, как во вселенной впервые появился Свет. Как эти звёзды. . .	Создание нейросети с PyTorch AI_Generated 19.06.2025 Ключевое преимущество PyTorch — его питоновская натура. В отличие от TensorFlow, который изначально был построен как статический вычислительный граф, PyTorch предлагает динамический подход. Это. . .	JWT аутентификация в ASP.NET Core UnmanagedCoder 18.06.2025 Разрабатывая веб-приложения, я постоянно сталкиваюсь с дилеммой: как обеспечить надежную аутентификацию пользователей без ущерба для производительности и масштабируемости? Классические подходы на. . .	Краткий курс по С# aaLeXAA 18.06.2025 Здесь вы найдете все необходимые функции чтоб написать програму на C# Задание 1: КЛАСС FORM 1 public partial class Form1 : Form { Spisok listin = new Spisok(); . . .	50 самых полезных примеров кода Python для частых задач py-thonny 17.06.2025 Эффективность работы разработчика часто измеряется не количеством написаных строк, а скоростью решения задач. Готовые сниппеты значительно ускоряют разработку, помогают избежать типичных ошибок и. . .
C# и продвинутые приемы работы с БД stackOverflow 17.06.2025 Каждый . NET разработчик рано или поздно сталкивается с ситуацией, когда привычные методы работы с базами данных превращаются в источник бессонных ночей. Я сам неоднократно попадал в такие ситуации,. . .	Angular: Вопросы и ответы на собеседовании Reangularity 15.06.2025 Готовишься к техническому интервью по Angular? Я собрал самые распространенные вопросы, с которыми сталкиваются разработчики на собеседованиях в этом году. От базовых концепций до продвинутых. . .	Архитектура Onion в ASP.NET Core MVC stackOverflow 15.06.2025 Что такое эта "луковая" архитектура? Термин предложил Джеффри Палермо (Jeffrey Palermo) в 2008 году, и с тех пор подход только набирал обороты. Суть проста - представьте себе лук с его. . .	Unity 4D GameUnited 13.06.2025 Четырехмерное пространство. . . Звучит как что-то из научной фантастики, правда? Однако для меня, как разработчика со стажем в игровой индустрии, четвертое измерение давно перестало быть абстракцией из. . .	SSE (Server-Sent Events) в ASP.NET Core и .NET 10 UnmanagedCoder 13.06.2025 Кажется, Microsoft снова подкинула нам интересную фичу в новой версии фреймворка. Работая с превью . NET 10, я наткнулся на нативную поддержку Server-Sent Events (SSE) в ASP. NET Core Minimal APIs. Эта. . .

@dzrkot zzzZZZ... 527 / 358 / 94 Регистрация: 11.09.2013 Сообщений: 2,041

	задачка попалась, не пойм у условия не полные? 20.12.2013, 10:28. Показов 665. Ответов 3 Метки нет (Все метки) Задача: Даны два множества точек на плоскости. Найти радиус и центр окружности, проходящей через n(n>=3) точек первого множества и содержащей строго внутри себя равное число точек первого и второго множества. помогаю тут одному товарисчу, естественно условия он и сам до конца не знает, так вот, сложилось ощущение, что задача в такой постановке решение имеет через раз, т.е. нету условий, которым должны удовлетворять эти множества, ни кол-во точек... по идее что надо сделать - сгенерировать точки(ясное дело...), потом в цикле искать точку, которая будет равноудалена от хотя бы от 3 точек 1ого подмножества, а дальше проверять и считать точки внутри окружности, но как-то что-то мне здесь не нравится... Не по теме: есть хочу ппц :((( 0

@dzrkot
	21.12.2013, 19:40 [ТС]
	Не по теме: ох, не стоила благодарности)) 0

Опции темы