Dado un entero S , la tarea es encontrar las coordenadas de un triángulo cuya área es (S / 2) .
Ejemplos:
Entrada: S = 4
Salida:
(0, 0)
(1000000000, 1)
(999999996, 1)Entrada: S = 15
Salida:
(0, 0)
(1000000000, 1)
(999999985, 1)
Acercarse:
- Se sabe que el área del triángulo cuyas coordenadas son (X1, Y1) , (X2, Y2) y (X3, Y3) está dada por A = ((X1 * Y2) + (X2 * Y3) + (X3 * Y1) – (X1 * Y3) – (X2 * Y1) – (X3 * Y2)) / 2 .
- Ahora fijando (X1, Y1) a (0, 0) da A = ((X2 * Y3) – (X3 * Y2)) / 2 .
- Se da que A = S/2 lo que implica S = (X2 * Y3) – (X3 * Y2) .
- Ahora fije (X2, Y2) a (10 9 , 1) y la ecuación se convierte en S = 10 9 * Y3 – X3 que se puede resolver tomando un valor entero de una variable que da el valor entero para la otra variable.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; const long MAX = 1000000000; // Function to find the triangle // with area = (S / 2) void findTriangle(long S) { // Fix the two pairs of coordinates long X1 = 0, Y1 = 0; long X2 = MAX, Y2 = 1; // Find (X3, Y3) with integer coordinates long X3 = (MAX - S % MAX) % MAX; long Y3 = (S + X3) / MAX; cout << "(" << X1 << ", " << Y1 << ")\n"; cout << "(" << X2 << ", " << Y2 << ")\n"; cout << "(" << X3 << ", " << Y3 << ")"; } // Driver code int main() { long S = 4; findTriangle(S); return 0; }
Java
// Java implementation of the approach class GFG { static final long MAX = 1000000000; // Function to find the triangle // with area = (S / 2) static void findTriangle(long S) { // Fix the two pairs of coordinates long X1 = 0, Y1 = 0; long X2 = MAX, Y2 = 1; // Find (X3, Y3) with integer coordinates long X3 = (MAX - S % MAX) % MAX; long Y3 = (S + X3) / MAX; System.out.println("(" + X1 + ", " + Y1 + ")"); System.out.println("(" + X2 + ", " + Y2 + ")"); System.out.println("(" + X3 + ", " + Y3 + ")"); } // Driver code public static void main (String[] args) { long S = 4; findTriangle(S); } } // This code is contributed by AnkitRai01
Python3
# Python3 implementation of the approach MAX = 1000000000; # Function to find the triangle # with area = (S / 2) def findTriangle(S) : # Fix the two pairs of coordinates X1 = 0; Y1 = 0; X2 = MAX; Y2 = 1; # Find (X3, Y3) with integer coordinates X3 = (MAX - S % MAX) % MAX; Y3 = (S + X3) / MAX; print("(", X1, ",", Y1, ")"); print("(", X2, ",", Y2, ")"); print("(", X3, ",", Y3, ")"); # Driver code if __name__ == "__main__" : S = 4; findTriangle(S); # This code is contributed by kanugargng
C#
// C# implementation of the above approach using System; class GFG { static readonly long MAX = 1000000000; // Function to find the triangle // with area = (S / 2) static void findTriangle(long S) { // Fix the two pairs of coordinates long X1 = 0, Y1 = 0; long X2 = MAX, Y2 = 1; // Find (X3, Y3) with integer coordinates long X3 = (MAX - S % MAX) % MAX; long Y3 = (S + X3) / MAX; Console.WriteLine("(" + X1 + ", " + Y1 + ")"); Console.WriteLine("(" + X2 + ", " + Y2 + ")"); Console.WriteLine("(" + X3 + ", " + Y3 + ")"); } // Driver code public static void Main (String[] args) { long S = 4; findTriangle(S); } } // This code is contributed by PrinciRaj1992
Javascript
<script> // Javascript implementation of the approach let MAX = 1000000000; // Function to find the triangle // with area = (S / 2) function findTriangle( S) { // Fix the two pairs of coordinates let X1 = 0, Y1 = 0; let X2 = MAX, Y2 = 1; // Find (X3, Y3) with integer coordinates let X3 = (MAX - S % MAX) % MAX; let Y3 = (S + X3) / MAX; document.write( "(" + X1 + ", " + Y1 + ")<br/>"); document.write( "(" + X2 + ", " + Y2 + ")<br/>"); document.write( "(" + X3 + ", " + Y3 + ")<br/>") } // Driver code let S = 4; findTriangle(S); // This code contributed by aashish1995 </script>
Producción:
(0, 0) (1000000000, 1) (999999996, 1)
Complejidad de tiempo: O(1)
Espacio Auxiliar: O(1)