Решение задачи "Центр тяжести" с Меньшиков

Без пояснения   Просмотров: 9


По координатам вершин многоугольника требуется найти координаты его центра тяжести. Стороны многоугольника друг с другом не соприкасаются (за исключением соседних - в вершинах) и не пересекаются. Площадь многоугольника не равна нулю.

Ограничения: число вершин 3 <= N <= 100 000, координаты вершин в декартовой системе координат целые и по модулю не превосходят 20 000.

Код

#include <iostream>
#include <cstdio>
#include <vector>
 
using namespace std;
 
const double eps = 1e-9;
double _fabs(double a)
{
    if (a<0) return -a;
    return a;
}
bool Equal(double a, double b)
{
    return _fabs(a-b) <= eps;
}
struct point
{
    double x, y;
    point(){}
    point(double X, double Y)
    {
        x = X;
        y = Y;
    }
    void input()
    {
        cin>>x>>y;
    }
    void output()
    {
        if (Equal(x,0)) x = 0;
        if (Equal(y,0)) y = 0;
        printf("%0.2f %0.2f",x,y);
    }
};
int n;
vector<point> mas;
void input()
{
    cin>>n;
    mas.resize(n);
    for (int i=0;i<n;i++)
        mas[i].input();
}
double findS(const point &a, const point &b, const point &c)
{
    return 0.5*(a.x*b.y + b.x*c.y + c.x *a.y - a.y*b.x - b.y*c.x - c.y*a.x);
}
void solve()
{
   
    double S = 0;
    double midX = 0;
    double midY = 0;
    for (int i=1;i<n-1;i++)
    {
        double curS = findS(mas[0], mas[i], mas[i+1]);
        S += curS;
        midX += curS * (mas[0].x + mas[i].x + mas[i+1].x) / 3;
        midY += curS * (mas[0].y + mas[i].y + mas[i+1].y) / 3;
    }
    point center(midX/S, midY/S);
    center.output();
}
int main()
{
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
 
    input();
    solve();
    return 0;
}
 
// Меньшиков. Тренировка 13.
// 13E. Сумма произведений [prodsum]
// O(N) по авторскому разбору
// ibelyaev: 07Jan2011
 
#include <iostream>
#include <cstdio>
#include <cmath>
 
using namespace std;
 
int n,s;
void input()
{
    cin>>n>>s;
}
int amount;
double eps = 1e-9;
void solve()
{
    // z = 0 amount
    // p = +1 amount
    // m = -1 amount
    int p;
    for (int z = 0; z<=n; z++)
    {
        int k = n - z;
        int a = 4;
        int b = -4*k;
        int c = k*k - k - 2*s;
 
        int d = b*b - 4*a*c;
        if (d<0) continue;
 
        int sqrtD = sqrt((double)d) + eps;
       
        if (sqrtD * sqrtD == d)
        {
            if ((-b + sqrtD) % (2*a) == 0){
                p = (- b + sqrtD) / (2*a);
                if (0<=p && z+p <= n){
                    amount++;
                    continue;
                }
            }
            if ((-b - sqrtD) % (2*a) == 0){
                p = (- b - sqrtD) / (2*a);
                if (0<=p && z+p <= n){
                    amount++;
                    continue;
                }               
            }           
        }
    }
    cout<<amount;
}
int main()
{
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
 
    input();
    solve();
    return 0;
}

         

 Администратор Photo Автор: Администратор


Отправить решение задачи
Чтобы отправить решение вам нужно войти в систему или зарегистрироваться

Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться