Punkty kratowe w trójkącie

Mam dany trójkąt o wierzchołkach w punktach kratowych. Czyli mam dane łącznie 6 współrzędnych - x1, y1, x2, y2, x3, y3. Jak zliczyć ilość punktów kratowych WEWNĄTRZ tego trójkąta?

1. Wewnątrz znaczy licząc z krawędzią trójkąta czy też nie?
2. Ja bym spróbowął policzyć ile jest w prostokącie wyznaczonym przez skrajne współrzędne i na tej podstawie wnioskował.

Wewnątrz, czyli nie licząc krawędzi. Próbowałem zrobić coś takiego - Najpierw liczę ile jest punktów wewnątrz prostokąta (wyznaczonego przez wierzchołki). Odejmuję od tego ilość punktów kratowych wewnętrznych w trójkątach prostokątnych (tych, które dopełniają trójkąt z treści zadania do prostokąta) -> Robię to tak, że liczę pole oraz ilość punktów brzegowych i podstawiam do wzoru Pick'a, czyli po przekształceniu W = (dx*dy)/2 - 1/2 * B + 1. Niestety mój kod nie działa :(. Poniżej zamieszczam go. Mógłbyś rzucić okiem? :).

#include<iostream>
#include<cstdio>
using namespace std;
int n, x1, x2, x3, y1, y2, y3, mxx, mxy, mnx, mny, wynik, dx1, dx2, dx3, dy1, dy2, dy3, pkp, pk1, pk2, pk3;
int mx(int a, int b, int c)
{
	if(a >= b && a >= c) return a;
	if(b >= a && b >= c) return b;
	return c;
}
int mn(int a, int b, int c)
{
	if(a <= b && a <= c) return a;
	if(b <= a && b <= c) return b;
	return c;
}
int NWD(int a, int b)
{
	int t;
	while(b != 0)
	{
		t = b;
		b = a%b;
		a = t;
	}
	return a;
}
int delta(int a, int b)
{
	if(a > b) return a-b;
	return b-a;
}
int main()
{
	ios_base::sync_with_stdio(0);
	cin >> n;
	for(int i = 1; i <= n; i++)
	{
		cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3;
		mxx = mx(x1, x2, x3); dx1 = delta(x1, x2); dy1 = delta(y1, y2);
		mxy = mx(y1, y2, y3); dx2 = delta(x1, x3); dy2 = delta(y1, y3);
		mnx = mn(x1, x2, x3); dx3 = delta(x2, x3); dy3 = delta(y2, y3);
		mny = mn(y1, y2, y3);
		pkp = (mxx - mnx - 1) * (mxy - mny - 1);
		if(dx1 != 0 && dy1 != 0) pk1 = ((dx1 * dy1) - NWD(dx1, dy1) - dx1 - dy1 + 2)/2;
		if(dx2 != 0 && dy2 != 0) pk2 = ((dx2 * dy2) - NWD(dx2, dy2) - dx2 - dy2 + 2)/2;
		if(dx3 != 0 && dy3 != 0) pk3 = ((dx3 * dy3) - NWD(dx3, dy3) - dx3 - dy3 + 2)/2;
		wynik = pkp - pk1 - pk2 - pk3;
		cout << wynik << endl;
		mxx = 0; dx1 = 0; dy1 = 0;
		mxy = 0; dx2 = 0; dy2 = 0;
		mnx = 0; dx3 = 0; dy3 = 0;
		mny = 0; wynik = 0;
		pkp = 0; pk1 = 0; pk2 = 0; pk3 = 0;
	}
	return 0;
}

A bierzesz pod uwagę punkty które leżą na krawędziach trójkąta (nie tylko dla prostokątnego gdzie pokrywają się z krawędziami prostokąta)? Powinieneś.

Poprawiłem kod, ale wciąż coś nie działa :(. Dla testu:
1
0 0 3 0 0 4
zwraca -5, a powinno 3

Bo zapewne wielokrotnie odejmujesz te same wierzchołki. Jak usuwasz wierzchołki na krawędziach trójkąta to bierzesz pod uwage że niektóre są wspólne? Bo mam wrażenie ze jednak nie. Że usuwasz osobno wierzchołki z jednej krawędzi, osobno z drugiej i osobno z trzeciej.

Istotna jest wydajność? Logicznie najprostszy algorytm działa dobrze :

        //tablica Point[3] wierzcholki zawiera wierzchołki badanego trójkąta
        int minX = ...
        int maxX = ...
        int minY = ...
        int maxY = ...
        int licznik = 0;
        pole = pole(wierzcholki[0],wierzcholki[1],wierzcholki[2]);
        for(int i=minX;i<=maxX;i++)
        {
            for(int j=minY;j<=maxY;j++)
            {
                Point p = new Point(i,j);
                if(contains(p))
                {
                    licznik++;
                }
            }
        }
        ...
        boolean contains(Point p)
        {
           double pole1 = pole(p,wierzcholki[0],wierzcholki[1]);
           double pole2 = pole(p,wierzcholki[0],wierzcholki[2]);
           double pole3 = pole(p,wierzcholki[2],wierzcholki[1]);
           if((pole1+pole2+pole3<=pole) && (pole1>0) && (pole2>0) && (pole3>0))
           {
               return true;
           }
           return false;
       }

Udało mi się nareszcie napisać ten program :D. Zrezygnowałem z dopełniania do prostokąta itd. i zastosowałem o wiele prostszy w implementacji sposób. Najpierw policzyłem pole trójkąta za pomocą iloczynu wektorowego (pole trójkąta to 1/2 * a * b * sin alfa, więc jak łatwo zauważyć -> połowa iloczynu wektorowego odcinka "a" oraz odcinka "b"). Wzór na iloczyn wektorowy wyznaczyłem z wyznacznika macierzy 3x3, której kolejne wiersze to (x1, y1, 1);(x2, y2, 1);(x3, y3, 1) metodą Sarrusa. Wyszło x1y2 + x2y3 + x3y1 - x3y2 - x1y3 - x2y1. Następnie zliczyłem ilość punktów brzegowych (czyli po prostu suma NWD różnic x'ów i y'ów dla każdego odcinka trójkąta). Na koniec, przekształciłem wzór Pick'a z postaci P = W + 1/2B - 1 do postaci W = P - 1/2B + 1 (czyli po wciągnięciu wszystkiego pod wspólny mianownik W = (P-B+1)/2) i z tego wyliczyłem ilość punktów kratowych wewnątrz trójkąta. Poniżej jest mój kod, może się komuś przyda ;)

#include<iostream>
#include<cstdio>
using namespace std;
long long int n, x1, x2, x3, y1, y2, y3, nwd1, nwd2, nwd3, wynik;
long double P, B;
long long int NWD(long long int a, long long int b)
{
    long long int t;
    while(b != 0)
    {
        t = b;
        b = a%b;
        a = t;
    }
    return a;
}
long long int abs(long long int a)
{
	if(a < 0) return (-a);
	else return a;
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3;
        nwd1 = NWD(abs(x1 - x2), abs(y1 - y2));
        nwd2 = NWD(abs(x1 - x3), abs(y1 - y3));
        nwd3 = NWD(abs(x2 - x3), abs(y2 - y3));
        B = nwd1 + nwd2 + nwd3;
        P = abs(x1*y2 + x2*y3 + x3*y1 - x3*y2 - x1*y3 - x2*y1);
        wynik = (P-B+2)/2;
        cout << wynik << endl;
        B = 0;
        P = 0;
        wynik = 0;
	    nwd3 = 0;
        nwd2 = 0;
        nwd1 = 0;
    }
    return 0;
}