Многоугольник на плоскости задан целочисленными координатами своих N вершин в декартовой системе координат (найти площадь многоугольника)

@BlackScorpioNnn · Регистрация: 14.04.2013

Студворк — интернет-сервис помощи студентам

Здравствуйте форумчане! Необходим совет)
собственно задача:
Многоугольник на плоскости задан целочисленными координатами своих N вершин в декартовой системе координат. Требуется найти площадь многоугольника. Стороны многоугольника не соприкасаются (за исключением соседних - в вершинах) и не пересекаются. Ограничения: 3<=N<=50000, координаты вершин целые и по модулю не превосходят 20000. При вводе: В первой строке находится число N. В следующих N строках находятся пары чисел - координаты точек. Если соединить точки в данном порядке, а также первую и последнюю точки, получится заданный многоугольник. При выводе: Вывести одно число - площадь многоугольника. Его следует округлить до ближайшего числа с одной цифрой после запятой.

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
#include<iostream>
using namespace std;
int main()
{
double s;
int n,min;
long int x[50000];
long int y[50000];
cin>>n;
for(int i=0;i<n;i++)
{
cin>>x[i]>>y[i];
}
x[n]=x[0];
y[n]=y[0];
 
min=y[0];
for(int i=1;i<n;i++)
if(min>y[i])min=y[i];
 
for(int i=0;i<n+1;i++)
y[i]=y[i]-min;
s=0.0;
for(int i=0;i<n;i++){
s=s+(((float)y[i+1]+(float)y[i])*((float)x[i+1]-(float)x[i])/2);
}
if(s<0)
s=-s;
cout<<s;
return 0;}

но на сайте проверки http://olimpic.asu.tusur.ru выдает Wrong answer on test 6

Ternsip · 31.05.2013, 22:20

BlackScorpioNnn,

C++
1
2
3
4
5
6
7
8
9
10
11
#include <cstdio>
#include <cmath>
int n, i; double ans;
struct { int x, y; } p[100001];
int main() {
     scanf("%d", &n);
     for (i = 0; i < n; ++i) scanf("%d %d", &p[i].x, &p[i].y);
     p[n] = p[0];
     for (i = 0; i < n; ++i) ans += (p[i+1].x - p[i].x) * (p[i+1].y + p[i].y);
     printf("%.1lf", abs(ans)/2.0);
}

@BlackScorpioNnn · 23.06.2013, 11:22 **[ТС]**

Спасибо большое не мог бы ты пожалуйста обьяснить строчку.

C++
1
p[n] = p[0];

Ternsip · 23.06.2013, 21:19

@BlackScorpioNnn, последняя вершина = первой, это её копия, для удобства.

@genreator · 18.04.2016, 21:49

А можете объяснить смысл вот этого

C++
1
p[100001];

@gurulTailan · 03.08.2020, 10:11

Есть код на питоне, на C++ очень легко переделать:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
def gcd(a, b):
    while b > 0:
        a, b = b, a % b
    return a
n = int(input())
ans = 0
xfirst, yfirst = map(int, input().split())
xprev, yprev = xfirst, yfirst
for i in range(n - 1):
    x, y = map(int, input().split())
    ans += gcd(abs(x - xprev), abs(y - yprev))
    xprev, yprev = x, y
ans += gcd(abs(x - xfirst), abs(y - yfirst))
print(ans)

@TheCalligrapher · 03.08.2020, 10:30

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

Есть код на питоне, на C++ очень легко переделать:

И что же по-вашему вычисляет этот код?

@Alestrange · 08.08.2020, 10:14

Спасибо большое! Код проходит все тесты. Пожалуйста, если вам не трудно, не могли вы бы объяснить его работу?

Новые блоги и статьи Все статьи Все блоги /
Модель здравосоХранения 6. ESG-повестка и устойчивое развитие; углублённый анализ кадрового бренда anaschu 31.03.2026 В прикрепленном документе раздумья о том, как можно поменять модель в будущем	10 пpимет, которые всегда сбываются Maks 31.03.2026 1. Чтобы, наконец, пришла маршрутка, надо закурить. Если сигарета последняя, маршрутка придет еще до второй затяжки даже вопреки расписанию. 2. Нaдоели зима и снег? Не надо переезжать. Достаточно. . .	Перемещение выделенных строк ТЧ из одного документа в другой Maks 31.03.2026 Реализация из решения ниже выполнена на примере нетипового документа "ВыдачаОборудованияНаСпецтехнику" с единственной табличной частью "ОборудованиеИКомплектующие" разработанного в конфигурации КА2. . . .	Functional First Web Framework Suave DevAlt 30.03.2026 Sauve. IO Апнулись до NET10. Из зависимостей один пакет, работает одинаково хорошо как в режиме проекта так и в интерактивном режиме. из сложностей - чисто функциональный подход. Решил. . .
Автоматическое создание документа при проведении другого документа Maks 29.03.2026 Реализация из решения ниже выполнена на нетиповых документах, разработанных в конфигурации КА2. Есть нетиповой документ "ЗаявкаНаРемонтСпецтехники" и нетиповой документ "ПланированиеСпецтехники". В. . .	Настройка движения справочника по регистру сведений Maks 29.03.2026 Решение ниже реализовано на примере нетипового справочника "ТарифыМобильнойСвязи" разработанного в конфигурации КА2, с целью учета корпоративной мобильной связи в коммерческом предприятии. . . .	Автозаполнение реквизита при выборе элемента справочника Maks 27.03.2026 Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. При выборе "Спецтехники" (Тип Справочник. Спецтехника), заполняется. . .	Сумматор с применением элементов трёх состояний. Hrethgir 26.03.2026 Тут. https:/ / fips. ru/ EGD/ ab3c85c8-836d-4866-871b-c2f0c5d77fbc Первый документ красиво выглядит, но без схемы. Это конечно не даёт никаких плюсов автору, но тем не менее. . . всё может быть. . .

Ternsip 670 / 198 / 29 Регистрация: 10.05.2012 Сообщений: 595
	23.06.2013, 21:19
	@BlackScorpioNnn, последняя вершина = первой, это её копия, для удобства. 0

@Alestrange 8 / 8 / 1 Регистрация: 25.06.2020 Сообщений: 5
	08.08.2020, 10:14
	Спасибо большое! Код проходит все тесты. Пожалуйста, если вам не трудно, не могли вы бы объяснить его работу? 0