Многоугольник на плоскости задан целочисленными координатами своих 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

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

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве 8Observer8 02.02.2026 Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .	Философия технологии iceja 01.02.2026 На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .	SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf 8Observer8 01.02.2026 Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .	SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли 8Observer8 30.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .
SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm 8Observer8 30.01.2026 Содержание блога Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .	SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 29.01.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .	Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT bedvit 28.01.2026 Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .	SDL3 для Android: Загрузка PNG с альфа-каналом с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 28.01.2026 Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .

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