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

Площадь многоугольника - C++

Восстановить пароль Регистрация
 
xGoooDx
0 / 0 / 0
Регистрация: 28.09.2015
Сообщений: 27
04.10.2015, 20:41     Площадь многоугольника #1
Всем добрый вечер!
Есть задача:
Заданы координаты n последовательных вершин многоугольника. Определить его площадь.

Входные данные

Первая строка содержит количество вершин многоугольника n. В следующих n строках через пробел заданы целочисленные координаты его последовательных вершин xi, yi. Известно, что 3 ≤ n ≤ 1000, -1000 ≤ x[i], y[i] ≤ 1000`.

Выходные данные

Площадь многоугольника S, вычисленная с точностью до трех десятичных знаков.

Написал код под нее, но выдает не тот ответ.
Подскажите пожалуйста, где я напортачил?
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;
 
int main() {
    unsigned int n, i;
    int x[1000], y[1000];
    double sum = 0, s;
    cin >> n;
    for (int i = 1; i<n; ++i) {
        for (int i = 1; i<n - 1; ++i) {
        }
        cin >> x[i] >> y[i];
        sum += abs((x[i] + x[(i + 1)]) * (y[i] + y[(i + 1)]));
    }
    cin >> sum;
    s = sum * 0.5;
    cout << fixed << setprecision(3) << s << endl;
    return 0;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
04.10.2015, 20:41     Площадь многоугольника
Посмотрите здесь:

Площадь многоугольника C (СИ)
Площадь многоугольника
Pascal ABC площадь многоугольника
Площадь многоугольника C++
Площадь многоугольника C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
PavelPol
21 / 21 / 10
Регистрация: 05.11.2014
Сообщений: 97
04.10.2015, 21:07     Площадь многоугольника #2
Если честно, не пойму что за алгоритм вы пытаетесь реализовать. Площадь многоугольника - не тривиальная задача.
Решение, которое приходит мне на ум - искать площади треугольников, состоящих из отрезка n(0) - n(1) .. n(N) - n(0) и смещенных осей координат. Затем все эти площади сложить. Площади треугольников считать либо по формуле, либо методом интегрирования.

Добавлено через 9 минут
Если ничего не путаю, должно работать так:
C++
1
2
3
4
5
for (int i = 0; i<n; i++) {
        cin >> x[i] >> y[i]; if (i == 0) continue;
        sum += 1.0 / 2.0 * sqrt(pow(abs(x[i] - x[i-1]), 2.0) + 
                                         pow(abs(y[i] - y[i-1]), 2.0)) * abs(y[i] - y[i-1]);
}
Barrent
 Аватар для Barrent
211 / 87 / 27
Регистрация: 04.05.2013
Сообщений: 260
Завершенные тесты: 1
04.10.2015, 21:25     Площадь многоугольника #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
#include "stdafx.h"
#include <Windows.h>
#include <math.h>
#include <iostream>
 
using namespace std;
 
class Point {
    //VARIABLES
    public: 
        int x;
        int y;
    //CONSTRUCTORS
    public: 
        Point(int x, int y) {           
            this->x = x;
            this->y = y;
        }
};
 
float TriangleSquare(Point& A, Point& B, Point& C);
float Distance(Point& A, Point& B);
 
int main()
{   
    //вершины выпуклого многоугольника
    const int n = 7;
    Point points[n]{ Point(0,0), Point(2,4), Point(6,5), Point(10,3), Point(11,-1), Point(7, -5), Point(3,4) };
 
    float square = 0;
    //перебор треугольников
    for (int i = 1; i < n - 1; i++) {
        square += TriangleSquare(points[0], points[i], points[i+1]);
    }
    cout << "Square: " << square << endl;
    system("pause");
    return 0;
}
 
float TriangleSquare(Point& A, Point& B, Point& C) {
    float AB = Distance(A, B);
    float BC = Distance(B, C);
    float AC = Distance(A, C);
    float p = (AB + BC + AC) / 2;               //половина периметра
    return sqrt(p*(p - AB)*(p - BC)*(p - AC));  //Герон
}
 
float Distance(Point& A, Point& B) {
    return sqrt(pow(A.x - B.x, 2) + pow(A.y - B.y, 2)); 
}
Миниатюры
Площадь многоугольника  
xGoooDx
0 / 0 / 0
Регистрация: 28.09.2015
Сообщений: 27
04.10.2015, 21:52  [ТС]     Площадь многоугольника #4
Цитата Сообщение от PavelPol Посмотреть сообщение
Если честно, не пойму что за алгоритм вы пытаетесь реализовать. Площадь многоугольника - не тривиальная задача.
Решение, которое приходит мне на ум - искать площади треугольников, состоящих из отрезка n(0) - n(1) .. n(N) - n(0) и смещенных осей координат. Затем все эти площади сложить. Площади треугольников считать либо по формуле, либо методом интегрирования.
Добавлено через 9 минут
Если ничего не путаю, должно работать так:
Код C++Выделить код
1
2
3
4
5
for (int i = 0; i<n; i++) {
* * * * cin >> x[i] >> y[i]; if (i == 0) continue;
* * * * sum += 1.0 / 2.0 * sqrt(pow(abs(x[i] - x[i-1]), 2.0) +
* * * * * * * * * * * * * * * * * * * * *pow(abs(y[i] - y[i-1]), 2.0)) * abs(y[i] - y[i-1]);
}
К сожалению, все равно неправильно считает
Ответ не тот и появилась еще одна графа ввода
Yandex
Объявления
04.10.2015, 21:52     Площадь многоугольника
Ответ Создать тему
Опции темы

Текущее время: 09:16. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru