Опытный
Профиль
Группа: Участник
Сообщений: 381
Регистрация: 29.1.2008
Где: Саратов
Репутация: 16
Всего: 18
|
Ладно, я утомился объяснять, ваша взяла. Вот код.  | Код | // класс "точка"
struct pt {
double x, y;
};
// класс "прямая"
struct line {
double a, b, c;
// строит прямую по двум точкам
line (pt p, pt q) {
a = p.y - q.y;
b = q.x - p.x;
c = - a * p.x - b * p.y;
double z = sqrt (a*a + b*b); // нормируем прямую, для увеличения точности
a /= z; b /= z; c /= z;
}
// вычисляет знак точки относительно полуплоскости
int sign (pt p) const {
double v = a * p.x + b * p.y + c;
return abs(v)<1E-9 ? 0 : v>0 ? +1 : -1;
}
};
// строит многоугольник, аппроксимирующий окружность
vector<pt> build (double x0, double y0, double r) {
const int N = 1000000; // число точек в многоугольнике (чем больше, тем точнее)
vector<pt> res (N);
r *= sqrt (2 * PI / N / sin (2 * PI / N)); // формула для пересчёта радиуса, чтобы площадь многоугольника совпала с площадью круга
for (int i=0; i<N; ++i) {
double ang = 2 * PI * i / N;
res[i].x = x0 + r * cos (ang);
res[i].y = y0 + r * sin (ang);
}
return res;
}
// строит полуплоскость, граница которой проходит через точки a и b, и так, что точка c лежит в этой полуплоскости (т.е. имеет знак "+1" относительно прямой)
line halfplane (pt a, pt b, pt c) {
line l (a, b);
if (l.sign (c) == -1) { // если c не попала в полуплоскость, умножим всё на -1, чтобы попала
l.a *= -1;
l.b *= -1;
l.c *= -1;
}
return l;
}
// вычисляет определитель матрицы 2x2
double det (double a, double b, double c, double d) {
return a * d - b * c;
}
// пересекает две прямые
pt intersect (line m, line n) {
double zn = det (m.a, m.b, n.a, n.b);
pt res = {
- det (m.c, m.b, n.c, n.b) / zn,
- det (m.a, m.c, n.a, n.c) / zn
};
return res;
}
// отсекает многоугольник полуплоскостью
vector<pt> cut (vector<pt> p, line l) {
vector<pt> res;
for (size_t i=0; i<p.size(); ++i) {
// рассматриваем текущую точку
if (l.sign (p[i]) >= 0)
res.push_back (p[i]);
// добавляем точку пересечения, если таковая есть
pt next = p[(i+1)%p.size()];
if (l.sign (p[i]) * l.sign (next) == -1)
res.push_back (intersect (l, line (p[i], next)));
}
return res;
}
// считает площадь многоугольника
double area (vector<pt> p) {
double s = 0;
for (size_t i=0; i<p.size(); ++i) {
pt next = p[(i+1)%p.size()];
s += (p[i].x + next.x) * (p[i].y - next.y);
}
return abs (s) / 2;
}
// решает задачу - для треугольника (p1,p2,p3) и окружности (x0,y0,r)
double solve (pt p1, pt p2, pt p3, double x0, double y0, double r) {
vector<pt> p = build (x0, y0, r);
p = cut (p, halfplane (p1, p2, p3));
p = cut (p, halfplane (p1, p3, p2));
p = cut (p, halfplane (p2, p3, p1));
return area (p);
} |
(тут не 30 строчек, но я попытался написать всё как можно подробнее) Точность - на моих тестах - порядка 15 знаков (хотя, наверное, на хитрых тестах будет похуже работать, но уж 6 знаков будет держать, инфа 100% ). |
Задача на геометрию. Требуется посчитать площадь пересечения. 
Загрузка ...
