Вычислительная геометрия на плоскости (си)

[rubakKa]

Многоугольник на плоскости задан целочисленными координатами своих N вершин в декартовой системе координат.Требуется найти площадь многоугольника. Стороны многоугольника не соприкасаются (за исключением соседних – в вершинах) и не пересекаются. В первой строке входного файла INPUT.TXT находится число N. В следующих N строках находятся пары чисел (Xi, Yi) – координаты точек. Если соединить точки в данном порядке, а также первую и последнюю точки, получится заданный многоугольник (3 ≤ N ≤ 50 000, -20 000 ≤ Xi, Yi ≤ 20 000). В выходной файл OUTPUT.TXT выведите одно число – площадь многоугольника. Его следует округлить до ближайшего числа с одной цифрой после запятой.

Как делать подскажите?

[V0id]

Для каждой пары вершин определить коэффициенты a и b уравнения прямой вида y=ax+b, проходящей через них, и вместе c границами области определения сохранить в массиве структур. Далее, построчно сканируя и пользуясь этим массивом, определять попадание внутрь многоугольника и подсчитывать число точек внутри него.

[rubakKa]

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

Для каждой пары вершин определить коэффициенты a и b уравнения прямой вида y=ax+b, проходящей через них, и вместе c границами области определения сохранить в массиве структур. Далее, построчно сканируя и пользуясь этим массивом, определять попадание внутрь многоугольника и подсчитывать число пикселей, внутри него.

Не поможете с кодом?

[V0id]

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

Не поможете с кодом?

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

[rubakKa]

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

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

Завтра уже сдавать нужно.. Врятли я успею
Но попытаюсь..

[V0id]

Очень поздно вы за это взялись! Если бы хотя бы в обед, можно было бы что-нибудь придумать, но теперь остается только нанять опытного фрилансера. Я же иду спать. Могу лишь подсказать, как рассчитываются коэффициенты. Для пары точек (x0,y0) и (x1,y1): a = (y1-y0)/(x1-x0), b = y0-a*x0, область определения отрезка: [min(x0,x1),max(x0,x1)].

[Гром]

Если я правильно понял, то почти то же самое: площадь семиугольника.
Если считать, что многоугольник выпуклый, то разбиваете его на треугольники, находите по формуле векторного произведения площадь каждого, суммируете, получаете площадь всего многоугольника.

[rubakKa]

Сообщение от Гром

Если я правильно понял, то почти то же самое: площадь семиугольника.
Если считать, что многоугольник выпуклый, то разбиваете его на треугольники, находите по формуле векторного произведения площадь каждого, суммируете, получаете площадь всего многоугольника.

Как здесь? http://www.cyberforum.ru/pascal/thread105431.html

Вот программа по алгоритму как в ссылке:

#include <stdio.h>
int main(){
FILE *in,*out;
in=fopen("input.txt","r");
out=fopen("output.txt","w");

float s;
int n,min;
char x[500];
char y[500];
fscanf(in,"%d",&n);
for(int i=0;i<n;i++)
fscanf(in,"%d %d",x[i], y[i]);
x[n+1]=x[0];
y[n+1]=y[0];
min=y[0];
for(int i=1;i<n;i++){
if(min>y[i]) 
min=y[i];
else 
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+((y[i+1]+y[i])*(x[i+1]-x[i])/2);
}
fprintf(out,"%d",s);
fclose(in);
fclose(out);
}

Компилируется, но вылетает при запуске. В чем ошибка?

Сдать нужно до 15:00 мск..

[Гром]

x[n+1]=x[0];
y[n+1]=y[0];

Это что такое?? Потенциальный выход за пределы диапазона, а если и нет, то, скорее всего, имелось в виду x[n] и y[n]

[V0id]

Сообщение от Гром

Если я правильно понял, то почти то же самое: площадь семиугольника.

Ага, я в полусне все перепутал... Действительно, обыкновенная сумма площадей входящих в объект треугольников.