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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
DAgot_
22 / 22 / 1
Регистрация: 03.01.2010
Сообщений: 68
#1

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

23.10.2010, 11:17. Просмотров 744. Ответов 2
Метки нет (Все метки)

Условие задачи:
Задача
Старик со старухой сидят за столом и пишут письма. На столе перед ними в точках с координатами (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++
определить принадлежность точки к окружности x^2+y^2&lt;=R^2 при x&lt;0

принадлежность точек - C++
Всем привет. Подскажите, кто сможет. Нужно определить к какой из областей на графике относится точка. Координаты точек вводим с...

Проверить принадлежность точки с заданными координатами заданному сегменту окружности - C++
Окружность на плоскости задана тремя лежащими на ней точками A, B, C. Фигура S представляет собой сегмент, ограниченный этой окружностью и...

Принадлежность заданных точек фигуре - C++
Составить программу,определяющую принадлежность 6-ти заданных точек заштрихованной фигуре. Сделал так,но надо через цикл for.Как это...

Программа, которая определяет принадлежность точек к полукружию - C++
Не используя оператор цикла составить программу, которая определяет, заданая точка (x, y) принадлежит полукружию, которое описывается...

Максимальное количество точек в окружности - C++
задача такая: дано кол-во кругов, кол-во точек ( все в координатах ) найти сколько раз заданные точки попадают в каждый круг и вывести...

Подскажи как подключить функцию проверки на принадлежность символов к моей программе - C++
Подскажи как подключить функцию проверки на принадлежность символов к моей программе. Вот сама функция. // Если x принадлежит строке A,...

Найти количество общих точек окружности и прямой - C++
Решить задачу в С++ Помогите пожалуйста =) Дана окружность и прямая. Окружность задается уранвением r²=x²+y². Уравнение прямой y=ax+b....

Количество целых точек в окружности с центром в (x, y) и радиусом R - C++
Задана окружность радиуса R с центром в точке (X,Y). Необходимо определить количество точек с целочисленными координатами, которые попадают...

С клаавиатуры вводятся координаты (x, y) пяти точек и радиус окружности. - C++
С клаавиатуры вводятся координаты (x, y) пяти точек и радиус окружности. Определить какие из точек удовлетворяют уравнению круга.


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru