1

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

#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));  
}  
0

2 ответа 2

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;
}

1
  • 3
    Вообще-то это две эквивалентные формулы, что у ТС, что у вас — просто у него при суммировании получается масса сокращений (x_i*y_i, вычисленное на одной итерации, сокращается с таким же членом на другой итерации). А по времени даже непонятно, что лучше — у него на одну итерацию сложение, вычитание и умножение, у вас - разность и два умножения...
    – Harry
    13 авг 2021 в 4:32
2

А это ничего, что в условии вершин может быть до 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());
}

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

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.