Ошибка в программе. Принадлежность точек окружности.

@DAgot_ · Регистрация: 03.01.2010

Студворк — интернет-сервис помощи студентам

Условие задачи:

Задача
Старик со старухой сидят за столом и пишут письма. На столе перед ними в точках с координатами (xi, yi) стоят N карандашей. Диаметр карандашей 0, и все они стоят вертикально. Старик и старуха решили разделить карандаши на две равные группы. Чтобы сделать это, старик берёт нитку и кладёт её на стол в форме окружности. Окружность должна проходить через три карандаша. Старик хочет, чтобы одна группа карандашей была в круге, а вторая вне круга.
Исходные данные
В первой строке ввода находится одно нечётное целое число 3 ≤ N ≤ 5000. В следующих N строках находятся координаты карандашей. Никакие три карандаша не лежат на одной прямой, и никакие четыре карандаша не лежат на одной окружности. Все координаты целые и по модулю не превосходят 108.
Результат
Выведите 6 целых чисел — координаты трёх карандашей, через которые пролегла нитка. Карандашей внутри круга должно быть (N−3)/2. На окружности должны лежать три указанных карандаша. Остальные карандаши, также (N−3)/2, должны лежать вне круга. Если решения нет, нужно вывести "No solution". Если решений больше одного, выведите любое из них.

Программа:

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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
/*--------------------------------------------------------------- БИБЛИОТЕКИ */
 
#include    <iostream>
#include    <fstream>
#include    <vector>
#include    <math.h>
 
 
/*------------------------------------------------------------------ ДЕФАЙНЫ */
 
 
/*------------------------------------------------------------------- КЛАССЫ */
 
// Класс "точка" (содержит значения координат точки)
class point{
 
public:
 
    double x;
    double y;
 
    point(): x(0), y(0){};
    point(double arg, double f): x(arg), y(f){};
    ~point(){};
};
 
// Класс "Окружность" (содержит значения координат центра окружности и  длины
// её радиуса)
class сircle{
 
public:
 
    double x;
    double y;
    double r;
 
    сircle(): x(0), y(0), r(1){};
    сircle(double arg, double f, double rad): x(arg), y(f), r(rad){};
    ~сircle(){};
};
 
 
/*------------------------------------------------------------------- ПРОЧЕЕ */
 
// Потоки ввода/вывода
std::ifstream in("input.txt");
std::ofstream out("output.txt");
 
сircle tempCircle;
 
int n;
 
int i, j, k;
 
double radius2;
 
int vkruge = 0, zakrugom = 0;
 
 
 
/*------------------------------------------------------------------ ФУНКЦИИ */
 
// вычисляет координаты центра окружности
void GetCircleWithThreePoints(point a, point b, point c){
    
    point temp;
    
    if(c.x == b.x){
        temp = a;
        a = b;
        b = temp;
    }
    else if(a.x == b.x){
        temp = c;
        c = b;
        b = temp;
    }
    
    double ma = (b.y - a.y) / (b.x - a.x);
    double mb = (c.y - b.y) / (c.x - b.x);
 
    tempCircle.x = (((ma*mb)*(a.y-c.y))+(mb*(a.x+b.x))-(ma*(b.x+c.x))) / (2*(mb-ma));
    tempCircle.y = (((a.x+b.x)/2)-tempCircle.x)/ma + (a.y+b.y)/2;
 
}
 
 
/*-------------------------------------------------------------- ТОЧКА ВХОДА */
 
int main(){
 
    // ввод количества точек
    in >> n;
 
    // массив для хранения координат точек
    point *v = new point[n];
    
    // заполнение массива
    for(i=0; i<n; i++)
        in >> v[i].x >> v[i].y;
 
    // перебор всех возможных комбинаций точек
    for(i=0; i<n; i++){
        for(j=i+1; j<n; j++){
            for(k=j+1; k<n; k++){
 
                vkruge = 0;
                zakrugom = 0;
 
                // получить координаты центра окружности
                GetCircleWithThreePoints(v[i], v[j], v[k]);
 
                // считает квадрат радиуса окружности
                radius2 = ((tempCircle.x-v[i].x)*(tempCircle.x-v[i].x)) + ((tempCircle.y-v[i].y)*(tempCircle.y-v[i].y));
 
                // перебор всех точек
                for(int z=0; z<n; z++){
                    // если точка принадлецит окружности
                    if(((tempCircle.x-v[z].x)*(tempCircle.x-v[z].x) + (tempCircle.y-v[z].y)*(tempCircle.y-v[z].y)) < radius2){
                        vkruge++;
                    }
                    // если не принадлежит
                    else if(((tempCircle.x-v[z].x)*(tempCircle.x-v[z].x) + (tempCircle.y-v[z].y)*(tempCircle.y-v[z].y)) > radius2){
                        zakrugom++;
                    }
                }
 
                // вывод количества точек в круге и за кругом а также координат центра окружности
                std::cout << "V kruge = " << vkruge << "\tCenter x = " << tempCircle.x ;
                std::cout << "\nZa krugom = " << zakrugom << "\tCenter y = " << tempCircle.y << "\n\n";
 
                // вывести искомую комбинацию
                if(vkruge == zakrugom && vkruge == (n-3)/2){
                    out << "( " << v[i].x << ", " << v[i].y << " )";
                    out << "\n";
                    out << "( " << v[j].x << ", " << v[j].y << " )";
                    out << "\n";
                    out << "( " << v[k].x << ", " << v[k].y << " )";
                    out << "\n\n";
                }
            
            }
        }
    }
 
    return 0;
}

Пример входных и выходных значений:

Вход

7
0 0
1 0
2 -1
2 1
1 1
0 2
-3 -1
Выход
0 0
1 0
2 1

Вопрос:

1. Почему на первых итерациях значения x и y центра окружности
одинаковы и равны 0.5 и -1.#IND?
2. Где ошибка?

Добавлено через 17 минут
P.S. Центр окружности считал по этой формуле: http://algolist.manual.ru/math... circle.php

@DAgot_ · 24.10.2010, 13:15 **[ТС]**

Помогите кто-нибудь, пожалуйста.

@easybudda · 24.10.2010, 15:02

Вывод можно покрасивше сделать, а так вот:

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 <cmath>
#include <cstdlib>
 
class Point {
    double x;
    double y;
public:
    Point() : x(0.0), y(0.0) {}
    Point(double _x, double _y) : x(_x), y(_y) {}
 
    void X(double _x) { x = _x; }
    double X() const { return x; }
    void Y(double _y) { y = _y; }
    double Y() const { return y; }
 
    double Distance(const Point & p) const {
        double dx = fabs(p.X() - x);
        double dy = fabs(p.Y() - y);
        return sqrt(dx * dx + dy * dy);
    }
};
 
class Circle {
    Point c;
    double r;
public:
    Circle() : r(0.0) {}
    Circle(double _x, double _y, double _r) : c(_x, _y), r(_r) {}
    Circle(const Point & p, double _r) : c(p), r(_r) {}
 
    void R(double _r) { r = _r; }
    double R() const { return r; }
    void X(double _x) { c.X(_x); }
    double X() const { return c.X(); }
    void Y(double _y) { c.Y(_y); }
    double Y() const { return c.Y(); }
 
    bool Inside(const Point & p) const {
        return c.Distance(p) < r;
    }
    bool OnBorder(const Point & p) const {
        return c.Distance(p) == r;
    }
};
 
std::istream & operator >> (std::istream & ist, Point & p){
    double x, y;
    ist >> x >> y;
    p.X(x);
    p.Y(y);
    return ist;
}
 
std::istream & operator >> (std::istream & ist, Circle & c){
    double x, y, r;
    ist >> x >> y >> r;
    c.X(x);
    c.Y(y);
    c.R(r);
    return ist;
}
 
std::ostream & operator << (std::ostream & ost, const Point & p){
    ost << p.X() << ' ' << p.Y();
    return ost;
}
 
std::ostream & operator << (std::ostream & ost, const Circle & c){
    ost << c.X() << ' ' << c.Y() << ' ' << c.R();
    return ost;
}
 
////////////////////////////////////////////
 
int main(){
    Circle c;
    Point * pArr;
    int cnt;
 
    std::cout << "Enter space separated circle coordinates and radius (X Y R)\n> ";
    std::cin >> c;
    std::cout << "Enter number of points: ";
    std::cin >> cnt;
    pArr = new Point [ cnt ];
    std::cout << "Enter space separated coordinates for " << cnt << " points (X Y)" << std::endl;
    for ( int i = 0; i < cnt; ++i ){
        std::cout << "Point #" << ( i + 1 ) << " > ";
        std::cin >> pArr[i];
    }
 
    std::cout << std::endl;
    std::cout << "Circle (X Y R): " << c << std::endl;
    std::cout << cnt << " points (X Y State):" << std::endl;
    for ( int i = 0; i < cnt; ++i )
        std::cout << pArr[i] << ( c.Inside(pArr[i]) ? " inside" : c.OnBorder(pArr[i]) ? " on border" : " outside" ) << std::endl;
 
    system("pause");
    return 0;
}

Новые блоги и статьи Все статьи Все блоги /
Архитектура слоя интернета для сервера-слоя. Hrethgir 11.04.2026 В продолжение https:/ / www. cyberforum. ru/ blogs/ 223907/ 10860. html Знаешь что я подумал? Раз мы все источники пишем в голове ветки, то ничего не мешает добавить в голову такой источник, который сам. . .	Подстановка значения реквизита справочника в табличную часть документа Maks 10.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: при выборе сотрудника (справочник Сотрудники) в ТЧ документа. . .	Очистка реквизитов документа при копировании Maks 09.04.2026 Алгоритм из решения ниже применим как для типовых, так и для нетиповых документов на самых различных конфигурациях. Задача: при копировании документа очищать определенные реквизиты и табличную. . .	модель ЗдравоСохранения 8. Подготовка к разному выполнению заданий anaschu 08.04.2026 https:/ / github. com/ shumilovas/ med2. git main ветка * содержимое блока дэлэй из старой модели теперь внутри зайца новой модели 8ATzM_2aurI
Блокировка документа от изменений, если он открыт у другого пользователя Maks 08.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа, разработанного в конфигурации КА2. Задача: запретить редактирование документа, если он открыт у другого пользователя. / / . . .	Система безопасности+живучести для сервера-слоя интернета (сети). Двойная привязка. Hrethgir 08.04.2026 Далее были размышления о системе безопасности. Сообщения с наклонным текстом - мои. А как нам будет можно проверить, что ссылка наша, а не подделана хулиганами, которая выбросит на другую ветку и. . .	Модель ЗдрввоСохранения 7: больше работников, больше ресурсов. anaschu 08.04.2026 работников и заданий может быть сколько угодно, но настроено всё так, что используется пока что только 20% kYBz3eJf3jQ	Дальние перспективы сервера - слоя сети с космологическим дизайном интефейса карты и логики. Hrethgir 07.04.2026 Дальнейшее ближайшее планирование вывело к размышлениям над дальними перспективами. И вот тут может быть даже будут нужны оценки специалистов, так как в дальних перспективах всё может очень сильно. . .

@DAgot_ 24 / 24 / 6 Регистрация: 03.01.2010 Сообщений: 68
	24.10.2010, 13:15 [ТС]
	Помогите кто-нибудь, пожалуйста. 0