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?
Punkty kratowe w trójkącie
- Rejestracja: dni
- Ostatnio: dni
- Postów: 50
0
- Rejestracja: dni
- Ostatnio: dni
- Lokalizacja: Space: the final frontier
- Postów: 26433
1
- Wewnątrz znaczy licząc z krawędzią trójkąta czy też nie?
- Ja bym spróbowął policzyć ile jest w prostokącie wyznaczonym przez skrajne współrzędne i na tej podstawie wnioskował.
- Rejestracja: dni
- Ostatnio: dni
- Postów: 50
0
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;
}
- Rejestracja: dni
- Ostatnio: dni
- Lokalizacja: Space: the final frontier
- Postów: 26433
1
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ś.
- Rejestracja: dni
- Ostatnio: dni
- Postów: 50
0
Poprawiłem kod, ale wciąż coś nie działa :(. Dla testu:
1
0 0 3 0 0 4
zwraca -5, a powinno 3
- Rejestracja: dni
- Ostatnio: dni
- Lokalizacja: Space: the final frontier
- Postów: 26433
1
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.
- Rejestracja: dni
- Ostatnio: dni
1
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;
}
- Rejestracja: dni
- Ostatnio: dni
- Postów: 50
0
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;
}