Решение задачи Точки в многоугольнике с Меньшиков

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


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

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

Код

#include <iostream>
#include <cstdio>
#include <vector>
 
using namespace std;
typedef long long INT;
struct point
{
    INT x,y;
    void input()
    {
        scanf("%lld %lld", &x, &y);
    }
};
vector<point> mas;
int n;
void input()
{
    cin>>n;
    mas.resize(n);
    for (int i=0;i<n;i++)
        mas[i].input();
}
inline INT _abs(INT a)
{
    if (a < 0)
        return -a;
    return a;
}
INT Square(point &a, point &b, point &c)
{
    return a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y);
}
INT gcd (INT a, INT b)
{
    return b?gcd(b,a%b):a;
}
INT findBP()
{
    INT res = 0;
    for (int i=0;i<n;i++)
    {
        INT dx = _abs(mas[i].x - mas[(i+1)%n].x);
        INT dy = _abs(mas[i].y - mas[(i+1)%n].y);
        res += gcd(dx,dy);
    }
    return res;
 
}
void solve()
{
    INT S = 0;
   
    for (int i=1;i<n-1;i++)
        S += Square(mas[0],mas[i],mas[i+1]);
   
    S = _abs(S) / 2;
 
    INT BorderPoints = findBP();
   
    INT InsidePoints  = S - BorderPoints/2 + 1;
    cout<<InsidePoints;
}
int main()
{
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
 
    input();
    solve();
    return 0;
}

         

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



Комментарии

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