E-Olymp:Площадь многоугольника

Question

Ссылка на задачу Решил задачу формулой трапеций,но некоторые тесты неверны.Не могу понять где ошибка.

#include <stdio.h>  
#define MAX 1002  
int x[MAX], y[MAX],n;  
double findArea(int *x, int *y)  
{  
double s = 0;  
x[n] = x[0]; y[n] = y[0];  
for(int i = 0; i < n; i++)  
s += (y[i+1] + y[i]) * (x[i+1] - x[i])/2.0;  
return (s < 0) ? -s : s;  
}  
int main(void){  
scanf("%d",&n);  
for(int i = 0; i < n; i++){  
scanf("%d %d",&x[i],&y[i]);}  
printf("%.3lf\n",findArea(x,y));  
}

Answer 1

А это ничего, что в условии вершин может быть до 50000, а вы выделяете память только для 1000?

Вот она и валится...

Я бы делал, кстати, так:

#include <stdio.h>
#define MAX 50005
int x[MAX], y[MAX],n;

double findArea()
{
    long long s = 0;
    for(int i = 0; i < n; i++)
        s += (y[i+1] + y[i]) * (x[i+1] - x[i]);
    if (s < 0) s = -s;
    return s/2.0;
}
int main(void){
    scanf("%d",&n);
    for(int i = 0; i < n; i++){
        scanf("%d %d",&x[i],&y[i]);}
    x[n] = x[0]; y[n] = y[0];
    printf("%.3lf\n",findArea());
}

Но это не принципиально...

Answer 2

Для этого есть очень простая формула площади многоугольника, достаточно обработать исключения, и работает лучше чем трапеции. Это формула площади Гаусса.

#include <iostream>
#include <iomanip>
#include <cmath>
#include <vector>
#include <set>
#include <string>
#include <algorithm>
#include <cctype>
#include <iterator>
#include <climits>
#include <complex>
#include <list>
#include <map>

using namespace std;
struct Vecs{
    double x, y;
};
struct Point{
    double x, y;
};

Vecs  makeVector(Point& a, Point & b){
    Vecs res ;
    res.x = b.x - a.x;
    res.y = b.y - a.y;
    return res;
}
long double dot(Vecs& a, Vecs& b){
    return a.x * b.x + a.y * b.y;
}
long double len(Vecs& a){
    return sqrt(a.x*a.x+a.y*a.y);
}
long double cos(Vecs& a, Vecs& b){
    return dot(a, b)/(len(a) * len(b));
}
inline void solve(){
    size_t size;
    int j;
    cin >> size;
    vector <Point> base;
    base.resize(size);
    for (int i = 0; i < size; i++) {
        cin >> base[i].x >> base[i].y;
    }
    long double ans_sum=0;
    for (int i = 0; i < size; i++) {
        j = i + 1;
        if (j >= size) j = 0;
        ans_sum += (base[i].x * base[j].y) - (base[j].x * base[i].y);
    }
    ans_sum = abs(ans_sum);
    ans_sum /= 2;
    cout.precision(10);
    cout << fixed;
    cout <<ans_sum << endl;
    return;
}
int main() {
    solve();
    return 0;
}

БЛОГ НА HUSL

E-Olymp:Площадь многоугольника

Ответы (2 шт):