Решение задачи "Граница многоугольника" с Меньшиков

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


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

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

Код

#include <iostream>
#include <cstdio>
#include <vector>
 
using namespace std;
 
int n;
vector<int> X,Y;
void input()
{
    cin>>n;
    X.resize(n);
    Y.resize(n);
    for (int i=0;i<n;i++)
        cin>>X[i]>>Y[i];
}
int abs(int a)
{
    if (a<0)
        return -a;
    return a;
}
int gcd(int a, int b)
{
    if (!b)
        return a;
    return gcd(b,a%b);
}
void solve()
{
    long long amount = n;
    for (int i=0;i<n;i++)
    {
        int dx = abs(X[i] - X[(i+1)%n]);
        int dy = abs(Y[i] - Y[(i+1)%n]);
        amount += gcd(dx,dy) - 1;
    }
    cout<<amount;
}
int main()
{
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
 
    input();
    solve();
    return 0;
}

         

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


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

Комментарии

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