площадь полигона

[boomeer]

Даны координаты точек, xi, yj.
По этим данным определить площадь фигуры.
Что то ума не приложу, разделим, из 1й вершины проведем ко всем линии, получатся треугольники, сложим их. Но там же получатся части захватывающие, которые не нужны. Как реализовать возможно?

Или быть может не треугольниками, свой вариант предложите...

[Stilet]

Так тут не все координаты нарисованы... Есть "углы" без точек. что с ними делать?

[sergey.d]

Рискну предложить такое:

#include <iostream>
#include <list>

struct Point
{
    double x;
    double y;
};

typedef std::list<Point> PointList;

struct CompY
{
    bool operator () (const Point &a, const Point &b) { return a.y < b.y; }
} cmp;

double area(PointList &pl)
{
    pl.sort(cmp);

    double x0, x1, y0;
    double a = 0;

    if(!pl.empty())
    {
        x0 = x1 = pl.front().x;
        y0 = pl.front().y;
        pl.pop_front();

        while(!pl.empty())
        {
            double x2 = pl.front().x;
            double y1 = pl.front().y;
            a += (x1 - x0) * (y1 - y0);
            y0 = y1;
            ((x2 < (x0 + x1) * 0.5) ? x0 : x1) = x2;
            pl.pop_front();
        }
    }

    return a;
}

int main(int, char *[])
{
    Point pts[] = { {0, 9}, {7, 9}, {5, 8}, {7, 8}, {0, 5}, {2, 4}, {5, 4}, {3, 0}, {6, 0} };
    PointList pl;

    for(unsigned int i = 0; i < sizeof pts / sizeof pts[0]; ++i) pl.push_back(pts[i]);
    std::cout << "Area: " << area(pl) << std::endl;

    return 0;
}

P.S. Точки в коде заданы левые, подставьте свои.

[boomeer]

Сообщение от Stilet

Так тут не все координаты нарисованы... Есть "углы" без точек. что с ними делать?

А эти точки и не даны. Если в оригинале, то там так "Даны прямоугольники которые могут пересекаться и находится внутри другого. Найти площадь которую они занимают вместе"

[boomeer]

Сообщение от sergey.d

Рискну предложить такое:

#include <iostream>
#include <list>

struct Point
{
    double x;
    double y;
};

typedef std::list<Point> PointList;

struct CompY
{
    bool operator () (const Point &a, const Point &b) { return a.y < b.y; }
} cmp;

double area(PointList &pl)
{
    pl.sort(cmp);

    double x0, x1, y0;
    double a = 0;

    if(!pl.empty())
    {
        x0 = x1 = pl.front().x;
        y0 = pl.front().y;
        pl.pop_front();

        while(!pl.empty())
        {
            double x2 = pl.front().x;
            double y1 = pl.front().y;
            a += (x1 - x0) * (y1 - y0);
            y0 = y1;
            ((x2 < (x0 + x1) * 0.5) ? x0 : x1) = x2;
            pl.pop_front();
        }
    }

    return a;
}

int main(int, char *[])
{
    Point pts[] = { {0, 9}, {7, 9}, {5, 8}, {7, 8}, {0, 5}, {2, 4}, {5, 4}, {3, 0}, {6, 0} };
    PointList pl;

    for(unsigned int i = 0; i < sizeof pts / sizeof pts[0]; ++i) pl.push_back(pts[i]);
    std::cout << "Area: " << area(pl) << std::endl;

    return 0;
}

P.S. Точки в коде заданы левые, подставьте свои.

Отлично, теперь бы в коде разобраться

[sergey.d]

Отлично, теперь бы в коде разобраться

Основная идея -- "закрашиваем" нашу фигуру плоской горизонтальной "кистью" переменной ширины снизу вверх. Начинаем с кисти 0-й ширины, меняем ширину каждый раз, встречая новую точку из числа заданных. Ну, а наиболее полное описание кода - это сам код