Então eu quero calcular o número de pontosdentro de qualquer triângulo dado. Eu sei que tenho que usar o Teorema de Pick, mas meu código acaba sendo ridiculamente longo com a quantidade de instruções if-else para testar cada caso. Eu tenho usado isso como um guia Quantos pontos inteiros dentro dos três pontos formam um triângulo?, mas, em seguida, acabar com isso (vértices é uma matriz de 3 matrizes. Cada matriz é as coordenadas (x, y) de um vértice do triângulo):
int maxX = Math.max(Math.max(vertices[0][0], vertices[1][0]), vertices[2][0]),
minX = Math.min(Math.min(vertices[0][0], vertices[1][0]), vertices[2][0]),
maxY = Math.max(Math.max(vertices[0][1], vertices[1][1]), vertices[2][1]),
minY = Math.min(Math.min(vertices[0][1], vertices[1][1]), vertices[2][1]);
int height = Math.abs(maxY - minY),
width = Math.abs(maxX - minX);
double area = Math.abs(((vertices[0][0] * (vertices[1][1] - vertices[2][1]
)) + (vertices[1][0] * (vertices[2][1] - vertices[0][1]))
+ vertices[2][0] * (vertices[0][1] - vertices[1][1])) / 2);
if ((vertices[0][0] == vertices[1][0]) && (vertices[0][1] == vertices[2][1]))
{
area = ((Math.abs(vertices[0][1] - vertices[1][1]) - 1) *
(Math.abs(vertices[0][0] - vertices[2][0]) - 1)) / 2;
}
else if ((vertices[0][0] == vertices[2][0]) && (vertices[0][1] == vertices[1][1]))
{
area = ((Math.abs(vertices[0][1] - vertices[2][1]) - 1) *
(Math.abs(vertices[0][0] - vertices[1][0]) - 1)) / 2;
}
else if ((vertices[1][0] == vertices[2][0]) && (vertices[1][1] == vertices[0][1]))
{
area = ((Math.abs(vertices[1][1] - vertices[2][1]) - 1) *
(Math.abs(vertices[1][0] - vertices[0][0]) - 1)) / 2;
}
else if ((vertices[1][0] == vertices[2][0]) && (vertices[1][1] == vertices[0][1]))
{
area = ((Math.abs(vertices[1][1] - vertices[2][1]) - 1) *
(Math.abs(vertices[1][0] - vertices[0][0]) - 1)) / 2;
}
else if(vertices[0][0] == vertices[1][0])
{
int b = Math.abs(vertices[0][1] - vertices[1][1]);
/*double dist1 = Math.sqrt(Math.pow(vertices[0][0] - vertices[2][0], 2) +
Math.pow(vertices[0][1] - vertices[2][1], 2)),
dist2 = Math.sqrt(Math.pow(vertices[1][0] - vertices[2][0], 2) +
Math.pow(vertices[1][1] - vertices[2][1], 2));*/
if (vertices[0][1] > vertices[1][1])
{
area = (width - 1) * (height - 1) /*- dist1 - dist2*/ - (((width - 1) *
(height - 1) /*- dist1*/) / 2) - (((width - 1) * (height - b - 1)
/*- dist2*/) / 2);
}
else if (vertices[0][1] < vertices[1][1])
{
area = (width - 1) * (height - 1) /*- dist1 - dist2*/ - (((width - 1) *
(height - 1) /*- dist2*/) / 2) - (((width - 1) * (height - b - 1)
/*- dist1*/) / 2);
}
}
else if(vertices[0][0] == vertices[2][0])
{
int b = Math.abs(vertices[0][1] - vertices[2][1]);
/*double dist1 = Math.sqrt(Math.pow(vertices[0][0] - vertices[1][0], 2) +
Math.pow(vertices[0][1] - vertices[1][1], 2)),
dist2 = Math.sqrt(Math.pow(vertices[2][0] - vertices[1][0], 2) +
Math.pow(vertices[2][1] - vertices[1][1], 2));*/
if (vertices[0][1] > vertices[2][1])
{
area = (width - 1) * (height - 1) /*- dist1 - dist2*/ - (((width - 1) *
(height - 1) /*- dist1*/) / 2) - (((width - 1) * (height - b - 1)
/*- dist2*/) / 2);
}
else if (vertices[0][1] < vertices[2][1])
{
area = (width - 1) * (height - 1) /*- dist1 - dist2*/ - (((width - 1) *
(height - 1) /*- dist2*/) / 2) - (((width - 1) * (height - b - 1)
/*- dist1*/) / 2);
}
}
else if(vertices[1][0] == vertices[2][0])
{
int b = Math.abs(vertices[1][1] - vertices[2][1]);
/*double dist1 = Math.sqrt(Math.pow(vertices[1][0] - vertices[0][0], 2) +
Math.pow(vertices[1][1] - vertices[0][1], 2)),
dist2 = Math.sqrt(Math.pow(vertices[2][0] - vertices[0][0], 2) +
Math.pow(vertices[2][1] - vertices[0][1], 2));*/
if (vertices[1][1] > vertices[2][1])
{
area = (width - 1) * (height - 1) /*- dist1 - dist2*/ - (((width - 1) *
(height - 1) /*- dist1*/) / 2) - (((width - 1) * (height - b - 1)
/*- dist2*/) / 2);
}
else if (vertices[1][1] < vertices[2][1])
{
area = (width - 1) * (height - 1) /*- dist1 - dist2*/ - (((width - 1) *
(height - 1) /*- dist2*/) / 2) - (((width - 1) * (height - b - 1)
/*- dist1*/) / 2);
}
}
else if(vertices[0][1] == vertices[1][1])
{
int b = Math.abs(vertices[0][0] - vertices[1][0]);
/*double dist1 = Math.sqrt(Math.pow(vertices[0][1] - vertices[2][0], 2) +
Math.pow(vertices[0][1] - vertices[2][1], 2)),
dist2 = Math.sqrt(Math.pow(vertices[1][0] - vertices[2][0], 2) +
Math.pow(vertices[1][1] - vertices[2][1], 2));*/
if (vertices[0][0] > vertices[1][0])
{
area = (width - 1) * (height - 1) /*- dist1 - dist2*/ - (((width - 1) *
(height - 1) /*- dist1*/) / 2) - (((width - 1) * (height - b - 1)
/*- dist2*/) / 2);
}
else if (vertices[0][0] < vertices[1][0])
{
area = (width - 1) * (height - 1) /*- dist1 - dist2*/ - (((width - 1) *
(height - 1) /*- dist2*/) / 2) - (((width - 1) * (height - b - 1)
/*- dist1*/) / 2);
}
}
else if(vertices[0][1] == vertices[2][1])
{
int b = Math.abs(vertices[0][0] - vertices[2][0]);
/*double dist1 = Math.sqrt(Math.pow(vertices[0][1] - vertices[1][0], 2) +
Math.pow(vertices[0][1] - vertices[1][1], 2)),
dist2 = Math.sqrt(Math.pow(vertices[2][0] - vertices[1][0], 2) +
Math.pow(vertices[2][1] - vertices[1][1], 2));*/
if (vertices[0][0] > vertices[2][0])
{
area = (width - 1) * (height - 1) /*- dist1 - dist2*/ - (((width - 1) *
(height - 1) /*- dist1*/) / 2) - (((width - 1) * (height - b - 1)
/*- dist2*/) / 2);
}
else if (vertices[0][0] < vertices[2][0])
{
area = (width - 1) * (height - 1) /*- dist1 - dist2*/ - (((width - 1) *
(height - 1) /*- dist2*/) / 2) - (((width - 1) * (height - b - 1)
/*- dist1*/) / 2);
}
}
else if(vertices[1][1] == vertices[2][1])
{
int b = Math.abs(vertices[1][0] - vertices[2][0]);
/*double dist1 = Math.sqrt(Math.pow(vertices[1][1] - vertices[0][0], 2) +
Math.pow(vertices[1][1] - vertices[0][1], 2)),
dist2 = Math.sqrt(Math.pow(vertices[2][0] - vertices[0][0], 2) +
Math.pow(vertices[2][1] - vertices[0][1], 2));*/
if (vertices[1][0] > vertices[2][0])
{
area = (width - 1) * (height - 1) /*- dist1 - dist2*/ - (((width - 1) *
(height - 1) /*- dist1*/) / 2) - (((width - 1) * (height - b - 1)
/*- dist2*/) / 2);
}
else if (vertices[1][0] < vertices[2][0])
{
area = (width - 1) * (height - 1) /*- dist1 - dist2*/ - (((width - 1) *
(height - 1) /*- dist2*/) / 2) - (((width - 1) * (height - b - 1)
/*- dist1*/) / 2);
}
}
else if (minX == vertices[0][0])
{
int a = 0,
b = 0;
/*double dist1 = 0,
dist2 = 0,
dist3 = 0;*/
if(Math.min(vertices[1][0], vertices[2][0]) == vertices[1][0])
{
a = width - (vertices[1][0] - vertices[0][0]);
b = height - (vertices [1][1] - vertices[0][1]);
/*dist1 = Math.sqrt(Math.pow(vertices[0][0] - vertices[1][0], 2) +
Math.pow(vertices[0][1] - vertices[1][1], 2));
dist2 = Math.sqrt(Math.pow(vertices[1][0] - vertices[2][0], 2) +
Math.pow(vertices[1][1] - vertices[2][1], 2));
dist3 = Math.sqrt(Math.pow(vertices[0][0] - vertices[2][0], 2) +
Math.pow(vertices[0][1] - vertices[2][1], 2));*/
}
else if(Math.min(vertices[1][0], vertices[2][0]) == vertices[2][0])
{
a = width - (vertices[2][0] - vertices[0][0]);
b = height - (vertices [2][1] - vertices[0][1]);
/*dist1 = Math.sqrt(Math.pow(vertices[0][0] - vertices[2][0], 2) +
Math.pow(vertices[0][1] - vertices[2][1], 2));
dist2 = Math.sqrt(Math.pow(vertices[1][0] - vertices[2][0], 2) +
Math.pow(vertices[1][1] - vertices[2][1], 2));
dist3 = Math.sqrt(Math.pow(vertices[0][0] - vertices[1][0], 2) +
Math.pow(vertices[0][1] - vertices[1][1], 2));*/
}
area = (width - 1) * (height - 1) /*- dist1 - dist2 - dist3*/ - (((a - 1)
* (b - 1) /*- dist1*/) / 2) - (((width - a - 1) * (height - 1)
/*- dist2*/) / 2) - (((width - 1) * (height - b - 1) /*- dist3*/) / 2);
}
else if (minX == vertices[1][0])
{
int a = 0,
b = 0;
/*double dist1 = 0,
dist2 = 0,
dist3 = 0;*/
if(Math.min(vertices[0][0], vertices[2][0]) == vertices[0][0])
{
a = width - (vertices[0][0] - vertices[1][0]);
b = height - (vertices [0][1] - vertices[1][1]);
/*dist1 = Math.sqrt(Math.pow(vertices[1][0] - vertices[0][0], 2) +
Math.pow(vertices[1][1] - vertices[0][1], 2));
dist2 = Math.sqrt(Math.pow(vertices[0][0] - vertices[2][0], 2) +
Math.pow(vertices[0][1] - vertices[2][1], 2));
dist3 = Math.sqrt(Math.pow(vertices[1][0] - vertices[2][0], 2) +
Math.pow(vertices[1][1] - vertices[2][1], 2));*/
}
else if(Math.min(vertices[0][0], vertices[2][0]) == vertices[2][0])
{
a = width - (vertices[2][0] - vertices[1][0]);
b = height - (vertices [2][1] - vertices[1][1]);
/*dist1 = Math.sqrt(Math.pow(vertices[1][0] - vertices[2][0], 2) +
Math.pow(vertices[1][1] - vertices[2][1], 2));
dist2 = Math.sqrt(Math.pow(vertices[0][0] - vertices[2][0], 2) +
Math.pow(vertices[0][1] - vertices[2][1], 2));
dist3 = Math.sqrt(Math.pow(vertices[0][0] - vertices[1][0], 2) +
Math.pow(vertices[0][1] - vertices[1][1], 2));*/
}
area = (width - 1) * (height - 1) /*- dist1 - dist2 - dist3*/ - (((a - 1)
* (b - 1) /*- dist1*/) / 2) - (((width - a - 1) * (height - 1)
/*- dist2*/) / 2) - (((width - 1) * (height - b - 1) /*- dist3*/) / 2);
}
else if (minX == vertices[2][0])
{
int a = 0,
b = 0;
/*double dist1 = 0,
dist2 = 0,
dist3 = 0;*/
if(Math.min(vertices[0][0], vertices[1][0]) == vertices[0][0])
{
a = width - (vertices[0][0] - vertices[2][0]);
b = height - (vertices [0][1] - vertices[2][1]);
/*dist1 = Math.sqrt(Math.pow(vertices[2][0] - vertices[0][0], 2) +
Math.pow(vertices[2][1] - vertices[0][1], 2));
dist2 = Math.sqrt(Math.pow(vertices[0][0] - vertices[1][0], 2) +
Math.pow(vertices[0][1] - vertices[1][1], 2));
dist3 = Math.sqrt(Math.pow(vertices[1][0] - vertices[2][0], 2) +
Math.pow(vertices[1][1] - vertices[2][1], 2));*/
}
else if(Math.min(vertices[0][0], vertices[1][0]) == vertices[1][0])
{
a = width - (vertices[1][0] - vertices[2][0]);
b = height - (vertices [1][1] - vertices[2][1]);
/*dist1 = Math.sqrt(Math.pow(vertices[2][0] - vertices[1][0], 2) +
Math.pow(vertices[2][1] - vertices[1][1], 2));
dist2 = Math.sqrt(Math.pow(vertices[0][0] - vertices[2][0], 2) +
Math.pow(vertices[0][1] - vertices[2][1], 2));
dist3 = Math.sqrt(Math.pow(vertices[0][0] - vertices[2][0], 2) +
Math.pow(vertices[0][1] - vertices[2][1], 2));*/
}
area = (width - 1) * (height - 1) /*- dist1 - dist2 - dist3*/ - (((a - 1)
* (b - 1) /*- dist1*/) / 2) - (((width - a - 1) * (height - 1)
/*- dist2*/) / 2) - (((width - 1) * (height - b - 1) /*- dist3*/) / 2);
}
Alguém poderia me ajudar a consertar o algoritmo ou me dar uma maneira mais fácil / melhor de fazer isso? Este código praticamente nunca funciona.
Desculpe pelo código longo, eu não sabia quais partes eu deveria adicionar, então coloquei todo o algoritmo.
Editar: Então eu mudei o algoritmo para isso (Graças ao MBo):
public static int answer(int[][] vertices)
{
int a = (Math.abs((vertices[1][0] - vertices[0][0]) * (vertices[2][1]
- vertices[0][1]) - (vertices[2][0] - vertices[0][0]) *
(vertices[1][1] - vertices[0][1]))) / 2,
b = pointsOnLine(vertices[0][0], vertices[0][1], vertices[1][0],
vertices[1][1]) + pointsOnLine(vertices[1][0],
vertices[1][1], vertices[2][0], vertices[2][1]) +
pointsOnLine(vertices[0][0], vertices[0][1],
vertices[2][0], vertices[2][1]),
area = (2 * a - 2 - b) / 2; // Also tried a + (b / 2) - 1;
return (int)area;
}
public static int pointsOnLine(int x0, int y0, int x1, int y1)
{
BigInteger b1 = BigInteger.valueOf(Math.abs(x1 - x0)),
b2 = BigInteger.valueOf(Math.abs(y1 - y0));
return b1.gcd(b2).intValue();
}
Mas eu nem sempre recebo a resposta certa. Fiz algo errado?
Respostas:
3 para resposta № 1Picks theorem:
Número de pontos de treliça dentro
i = (2*A + 2 - b)/2
onde A é a área do triângulo, b é o número de pontos da rede nas bordas
Área através do crossproduct:
2*A = Abs (V[1].x-V[0].x)*(V[2].y-V[0].y) - (V[2].x-V[0].x)*(V[1].y-V[0].y))
NumPoints na borda entre os pontos (x0, y0) - (x1, y1), incluindo o primeiro ponto, excluindo o último (GCD é Grande Divisor Comum):
function PointsOnLine(x0, y0, x1, y1) = GCD(Abs(x2-x1), Abs(y2-y1))
para todas as arestas:
b = PointsOnLine(V[0].x, V[0].y, V[1].x, V[1].y) +
PointsOnLine(V[1].x, V[1].y, V[2].x, V[2].y) +
PointsOnLine(V[0].x, V[0].y, V[2].x, V[2].y)
Agora você pode obter i
2 para resposta № 2
Com base na resposta do @Mbo: [EDITADO]
private static long gcd(long n0, long n1) {
long a = n0;
long b = n1;
while (a != 0) {
long temp = a;
a = b % a;
b = temp;
}
return b;
}
public static long pointOnLine(long[][] vertices) {
return gcd(Math.abs(vertices[0][0] - vertices[1][0]),
Math.abs(vertices[0][1] - vertices[1][1])) +
gcd(Math.abs(vertices[1][0] - vertices[2][0]),
Math.abs(vertices[1][1] - vertices[2][1])) +
gcd( Math.abs(vertices[2][0] - vertices[0][0]),
Math.abs(vertices[2][1] - vertices[0][1]));
}
public static long area(long[][] vertices) {
return Math.abs((vertices[1][0] - vertices[0][0]) * (vertices[2][1] - vertices[0][1])
- (vertices[2][0] - vertices[0][0]) * (vertices[1][1] - vertices[0][1]));
}
public static void main(String[] args) {
long[][] vertices = {{91207, 89566}, {-88690, -83026}, {67100, 47194}};
//long[][] vertices = {{2,3}, {6,9}, {10,160}};
long i = (area(vertices) + 2 - pointOnLine(vertices)) / 2;
System.out.println("points: " + i);
}