Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

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

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

23.10.2010, 11:17. Просмотров 775. Ответов 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/equation/circle.php
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
23.10.2010, 11:17
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Ошибка в программе. Принадлежность точек окружности. (C++):

По заданным координатам центра окружности и ее радиусу определить координаты точек пересечения окружности с осями координат. - C++
По заданным координатам центра окружности и ее радиусу определить координаты точек пересечения окружности с осями координат.

Задать массив точек, и определить радиус и центр окружности, на которой лежит наибольшее число точек - C++
Необходимо задать массив точек и определить радиус и центр окружности на которой лежит наибольшее число точек +(еще надо вывести на экран...

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

Определить принадлежность точки к окружности - C++
определить принадлежность точки к окружности x^2+y^2&lt;=R^2 при x&lt;0

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

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

2
DAgot_
22 / 22 / 1
Регистрация: 03.01.2010
Сообщений: 68
24.10.2010, 13:15  [ТС] #2
Помогите кто-нибудь, пожалуйста.
0
easybudda
Модератор
Эксперт CЭксперт С++
9693 / 5643 / 962
Регистрация: 25.07.2009
Сообщений: 10,847
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;
}
1
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
24.10.2010, 15:02
Привет! Вот еще темы с ответами:

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

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

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

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


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

Или воспользуйтесь поиском по форуму:
3
Ответ Создать тему
Опции темы

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