Форум программистов, компьютерный форум CyberForum.ru

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

Восстановить пароль Регистрация
 
DAgot_
 Аватар для DAgot_
22 / 22 / 1
Регистрация: 03.01.2010
Сообщений: 68
23.10.2010, 11:17     Ошибка в программе. Принадлежность точек окружности. #1
Условие задачи:
Задача
Старик со старухой сидят за столом и пишут письма. На столе перед ними в точках с координатами (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/maths/geom...ion/circle.php
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
23.10.2010, 11:17     Ошибка в программе. Принадлежность точек окружности.
Посмотрите здесь:

принадлежность точек C++
C++ определить принадлежность точки к окружности
координаты точек пересечения прямой y=kx+b и окружности радиуса R C++
C++ Определить радиус и центр наибольшей окружности в области заданных точек, внутри которой нет точек
C++ По заданным координатам центра окружности и ее радиусу определить координаты точек пересечения окружности с осями координат.
C++ Программа, которая определяет принадлежность точек к полукружию
Задать массив точек, и определить радиус и центр окружности, на которой лежит наибольшее число точек C++
C++ Максимальное количество точек в окружности

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
DAgot_
 Аватар для DAgot_
22 / 22 / 1
Регистрация: 03.01.2010
Сообщений: 68
24.10.2010, 13:15  [ТС]     Ошибка в программе. Принадлежность точек окружности. #2
Помогите кто-нибудь, пожалуйста.
easybudda
Модератор
Эксперт С++
 Аватар для easybudda
9371 / 5421 / 914
Регистрация: 25.07.2009
Сообщений: 10,423
24.10.2010, 15:02     Ошибка в программе. Принадлежность точек окружности. #3
Вывод можно покрасивше сделать, а так вот:
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;
}
Yandex
Объявления
24.10.2010, 15:02     Ошибка в программе. Принадлежность точек окружности.
Ответ Создать тему
Опции темы

Текущее время: 02:23. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru