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

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

Новые блоги и статьи Все статьи Все блоги /
PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Access VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .

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