Привет. Прошу помощи. В общем задача: на координатной плоскости задается отрезок с началом в точке А и с концом в точке В. Также задаются круги (можно и 1 круг) с центрами в точках M1,M2,M3,...M100 и с радиусами R1,R2,R3,...,R100. Нужно проверить, принадлежит ли какая-либо точка отрезка заданной (заданным) окружностям.
В общем-то это задача из олимпиады, код компилируется на сервере. Мой код: http://ideone.com/J5MJEH
double xA, yA, xB, yB;
int count = 0;
int n;
cin >> xA >> yA >> xB >> yB; // Координаты A и B отрезка:
cin >> n; // Количество окружностей
double * * Arr = new double * [3]; // Задаем массив для кругов, в каждой строчке которого будут хранится x,y,r круга
for (int i = 0; i < n; i++)
Arr[i] = new double[3];
for (int i = 0; i < n; i++) {
for (int j = 0; j < 3; j++) {
cin >> Arr[i][j];
}
}
double r12 = sqrt((xB - xA) * (xB - xA) + (yB - yA) * (yB - yA)); // Длина отрезка от A до B
for (int i = 0; i < n; i++) {
double r1 = sqrt((Arr[i][0] - xA) * (Arr[i][0] - xA) + (Arr[i][1] - yA) * (Arr[i][1] - yA)); // Длина отрезка от т. M до A
double r2 = sqrt((Arr[i][0] - xB) * (Arr[i][0] - xB) + (Arr[i][1] - yB) * (Arr[i][1] - yB)); // Длина отрезка от т. M до B
if (((r12 * r12 + r1 * r1) - r2 * r2) >= 0 && ((r12 * r12 + r2 * r2) - r1 * r1) >= 0) { // Если перпендикуляр опущенный на прямую, проведенную через A u B лежит на отрезке AB, то проверяем, равен или больше ли радиус окружности
double d = (abs((yB - yA) * Arr[i][0] + (xB - xA) * Arr[i][1] + (xA * yB - yA * xB))) / sqrt((yB - yA) * (yB - yA) + (xB - xA) * (xB - xA));
if ((Arr[i][2] - d) >= 0) {
count++;
}
} else { // Иначе, если перпендикуляр опущенный на прямую лежит вне отрезка, то проверяем, равен или больше ли радиус одному из отрезков от точки М до А или В
if ((Arr[i][2] - r1) >= 0 || (Arr[i][2] - r2) >= 0) {
count++;
}
}
}
cout << count;
В комментариях кода написал, что,где, как нахожу.
То, как определить, падает ли перпендикуляр на отрезок, я взял отсюда: http://algolist.manual.ru/maths/geom/misc/perp.php, а именно неравенства: B2 <= A2 + C2, C2 <= A2 + B2.
В общем-то программа работает, но, вероятно, не всегда правильно. Уже достаточно много перепробовал тестовых примером, всё правильно определяет. Но, когда отправляю решение на сервер олимпиады, сервер говорит: "Wrong Answer". Я все грешу на типы. Сможете помочь?
Ответ
Вы не проверяете случай, когда часть отрезка лежит в одной окружности, а часть - в другой. Например, A(10, 10), B(10, 20), M1(10, 10), R1(5), M2(10, 20), R2(5). тут половина отрезка лежит в первой окружности, а половина - во второй.
http://ideone.com/TdMCuz
Я бы предложил следующий алгоритм. Для каждой окружности проверяем, лежит ли отрезок в ней полностью (т. е. лежат ли оба конца отрезка внутри окружности). Если да, то ответ - "да", выходим. Если оба конца отрезка вне окружности, переходим к следующей окружности. Если один конец внутри, а другой - снаружи, то обезаем отрезок, оставляя только ту его часть, что снаружи, и продолжаем проверки. Если после проверки всех окружностей остался ненулевой участок отрезка, ответ - "нет".
