Identificar la sección cónica

13

Dados 5 puntos distintos en un plano bidimensional, determine el tipo de sección cónica formada por los puntos. La salida será uno de circle, hyperbola, ellipse, o parabola.

Reglas

  • Los puntos estarán en posición lineal general, lo que significa que no hay tres puntos colineales y, por lo tanto, la cónica que los atraviesa será única.
  • Las coordenadas de los 5 puntos serán números decimales entre -10 y 10, inclusive.
  • La precisión de los valores decimales / flotantes debe ser la precisión del tipo flotante / decimal nativo de su idioma. Si su idioma / tipo de datos es de precisión arbitraria, puede usar 12 dígitos después del punto decimal como la precisión máxima requerida, redondeando hacia cero (por ejemplo 1.0000000000005 == 1.000000000000).
  • La capitalización de la producción no importa.
  • La salida ellipsecuando la sección cónica es en realidad un círculo no está permitida. Todos los círculos son elipses, pero debe generar el más específico.

En imprecisiones y precisión de coma flotante:

Estoy tratando de hacer esto lo más simple posible, para que los problemas con las imprecisiones de coma flotante no se interpongan en el camino. El objetivo es, si el tipo de datos fuera "valor de precisión infinita mágico" en lugar de flotante / doble, entonces todo funcionaría perfectamente. Pero, dado que el "valor de precisión infinita mágico" no existe, usted escribe un código que asume que sus valores son de precisión infinita, y cualquier problema que surja como resultado de imprecisiones de coma flotante son características, no errores.

Casos de prueba

(0, 0), (1, 5), (2, 3), (4, 8), (9, 2) => hyperbola
(1.2, 5.3), (4.1, 5.6), (9.1, 2.5), (0, 1), (4.2, 0) => ellipse
(5, 0), (4, 3), (3, 4), (0, 5), (0, -5) => circle
(1, 0), (0, 1), (2, 1), (3, 4), (4, 9) => parabola
Mego
fuente
2
Para flotantes, las salidas como circleparecen requerir la verificación de la igualdad de flotante para distinguirla de una elipse muy redonda. ¿Qué precisión debemos asumir aquí?
xnor
1
@Mego ¿Por qué no permitir la versión entera del problema para todos los idiomas, pero con un rango más amplio, por ejemplo, -10000 a 10000.
orlp
1
¿estás seguro de que el caso de prueba cuatro es correcto? desmos: desmos.com/calculator/fmwrjau8fd
Maltysen
2
Además, 3 también se ve mal: desmos.com/calculator/tkx1wrkotd
Maltysen
1
Creo que está subestimando los problemas con la precisión de FP, y eso lleva a una respuesta como esta codegolf.stackexchange.com/a/77815/21348
edc65

Respuestas:

2

Matlab, 154 bytes

p=input();c=null([p.^2 prod(p,2) p 1+p(:,1)*0]),s={'circle' 'ellipse' 'parabola' 'hyperbola'};s{3+sign(c(3)^2-4*c(1)*c(2))-~max(abs(c(3)),abs(c(1)-c(2)))}

Guardado algunos bytes gracias a las sugerencias de Suever.

Toma entrada como [x1 y1;x2 y2;x3 y3; etc]. Esto utilizó una matriz de Vandermonde, y encuentra la base de su espacio nulo, que siempre será un solo vector. Luego calcula el discriminante y lo usa para hacer un índice entre 1 y 4 que se usa para obtener la cadena.

Sin golf:

p=input();
c=null([p.^2 prod(p')' p ones(length(p),1)]);
s={'circle' 'ellipse' 'parabola' 'hyperbola'};
s{3+sign(c(3)^2-4*c(1)*c(2))-~max(abs(c(3)),abs(c(1)-c(2)))}

La sign(...)parte calcula el discriminante, dando 1 si es positivo (hipérbola), -1 si es negativo (elipse) y 0 si es 0 (parábola). El max(...)resta 1 de distancia si es un círculo. Las matrices de Matlab tienen un índice, así que agregue 3 para obtener los valores 1, 2, 3, 4 y úselo para indexar la matriz de nombres de secciones cónicas.

David
fuente
1
En lugar de comparar max() == 0, puede simplificar a~max()
Suever
1
También en lugar de lo ones(length(p),1)que podría hacer1+p(:,1)*0
Suever
Saludos, la max()cosa fue tonta de mi parte, ¡tuve comparaciones allí antes y obviamente me volví perezoso! Esa forma de obtenerla también oneses muy agradable.
David
14

JavaScript (ES6), 316323347

p=>[1,2,4].some(x=>(d=D(Q=[[x&1,x&2,x&4,0,0,0],...p.map(([x,y])=>[x*x,x*y,y*y,x,y,1])]))?[a,b,c]=Q.map((v,i)=>D(Q.map((r,j)=>(r=[...r],r[i]=x*!j,r)))/d):0,D=m=>m[1]?m[0].reduce((r,v,i)=>r+(i&1?-v:v)*D(m.slice(1).map(r=>r.filter((a,j)=>j-i))),0):m)&&(d=b*b-4*a*c)?d<0?!b&c==a?'Circle':'Ellipse':'Hyperbola':'Parabola'

Cualquier lenguaje más adecuado para manejar la matriz y el determinante debería tener una mejor puntuación (APL, J, CJAM, Jelly)

Referencias: forma general de una cónica , cinco puntos determinan una cónica , sistema de ecuaciones lineales , determinante

En el plano cartesiano, la ecuación general de una cónica es

A*x*x + B*x*y + C*y*y + D*x + E*y + F = 0 

Tener A, B o C no es igual a 0 (de lo contrario, es una línea recta)

A ... F hay seis incógnitas por encontrar. Con cinco pares de (x, y) podemos construir un sistema lineal con cinco ecuaciones, y la escala elimina una dimensión. Es decir, podemos establecer uno de A, B o C en 1 si no es 0 (y sabemos que al menos uno no es 0).

Construyo e intento resolver 3 sistemas: primero intento A = 1. Si no se puede resolver, entonces B = 1, luego C. (Podría haber una mejor manera, pero esa es mi mejor en ese momento)

Teniendo los valores de A, B, C podemos clasificar la cónica mirando el discriminante d=B*B-4*A*C

  • d == 0 -> parábola
  • d> 0 -> hipérbola
  • d <0 -> elipse, particularmente (A == C y B == 0) -> círculo

Menos golf

F=p=>(
  // Recursive function to find determinant of a square matrix
  D=m=>m[1]
    ?m[0].reduce((r,v,i)=>r+(i&1?-v:v)*D(m.slice(1).map(r=>r.filter((a,j)=>j-i))),0)
    :m,
  // Try 3 linear systems, coefficients in Q
  // Five equation made from the paramaters in p
  // And a first equation with coefficient like k,0,0,0,0,0,1 (example for A)  
  [1,2,4].some(
    x => (
      // matrix to calc the determinant, last coefficient is missing at this stage
      Q = [ 
        [x&1, x&2, x&4, 0,0,0] // first one is different
        // all other equations built from the params 
        ,...p.map( ([x,y]) => [x*x, x*y, y*y, x, y, 1] )
      ],
      d = D(Q), // here d is the determinant
      d && ( // if solvable  then d != 0
        // add missing last coefficient to Q
        // must be != 0 for the first row, must be 0 for the other
        Q.map( r=> (r.push(x), x=0) ),
        // solve the system (Cramer's rule), I get all values for A...F but I just care of a,b,c
        [a,b,c] = Q.map((v,i)=>D(Q.map(r=>(r=[...r],r[i]=r.pop(),r))) / d),
        d = b*b - 4*a*c, // now reuse d for discriminant
        d = d<0 ? !b&c==a ? 'Circle' : 'Ellipse' // now reuse d for end result
        : d ? 'Hyperbola' : 'Parabola'
      ) // exit .some if not 0
    ), d // .some exit with true, the result is in d
  )  
)

Prueba

F=p=>[1,2,4].some(x=>(d=D(Q=[[x&1,x&2,x&4,0,0,0],...p.map(([x,y])=>[x*x,x*y,y*y,x,y,1])]))?[a,b,c]=Q.map((v,i)=>D(Q.map((r,j)=>(r=[...r],r[i]=x*!j,r)))/d):0,D=m=>m[1]?m[0].reduce((r,v,i)=>r+(i&1?-v:v)*D(m.slice(1).map(r=>r.filter((a,j)=>j-i))),0):m)&&(d=b*b-4*a*c)?d<0?!b&c==a?'Circle':'Ellipse':'Hyperbola':'Parabola'

console.log=(...x)=>O.textContent+=x+'\n'

;[
 [[0, 0], [1, 5], [2, 3], [4, 8], [9, 2]]
,[[1.2, 5.3],[4.1, 5.6], [9.1, 2.5], [0, 1], [4.2, 0]]
,[[5, 0], [4, 3], [3, 4], [0, 5], [0, -5]]
,[[1, 0], [0, 1], [2, 1], [3, 4], [4, 9]]
].forEach(t=>console.log(t.join`|`+' => '+F(t)))
<pre id=O></pre>

edc65
fuente
2
¡Esto es realmente lindo! ¡Excelente trabajo!
Alex A.
2

Python - 234 bytes

import numpy as n
x=input()
d=[n.linalg.det(n.delete(n.array([[i*i,i*j,j*j,i,j,1]for i,j in x]),k,1))for k in range(6)]
t=d[1]**2-4*d[0]*d[2]
print"hyperbola"if t>0else"parabola"if t==0else"circle"if d[1]==0and d[0]==d[2]else"ellipse"

Nunca imprimo circleo parabolaporque ty d[1]nunca pego exactamente 0, pero OP dijo que estaba bien.

Maltysen
fuente
1

C, 500

Mi respuesta de JavaScript se transfirió a C. Solo para ver si se puede hacer.

Uso: lea 10 valores de la entrada estándar

echo 1 0 0 1 2 1 3 4 4 9 | cónico

Salida:

Parábola

Prueba (ideona)

double D(m,k)double*m;{double t=0;for(int s=1,b=1,x=0;x<6;x++,b+=b)k&b||(t+=s*m[x]*(k+b>62?1:D(m+6,k+b)),s=-s);return t;}i,u,h;double m[36],*t=m+6,w[6],s[3],b,d;main(){for(;i++<5;*t++=d*d,*t++=d*b,*t++=b*b,*t++=d,*t++=b,*t++=1)scanf("%lf%lf",&d,&b);for(u=4;u;u/=2)for(m[0]=u&1,m[1]=u&2,m[2]=u&4,d=D(m,0),h=0;d&&h<3;h++){for(i=0;i<6;i++)w[i]=m[i*6+h],m[i*6+h]=i?0:u;s[h]=D(m,0)/d;for(;i--;)m[i*6+h]=w[i];}b=s[1];d=b*b-4*s[0]*s[2];puts(d?d<0?!b&(s[2]==s[0])?"Circle":"Ellipse":"Hyperbola":"Parabola");}

Menos golf

// Calc determinant of a matrix of side d
// In the golfed code, d is fix to 6
double D(m, d, k)
double*m;
{
    int s = 1, b = 1, x = 0;
    double t = 0;
    for (; x < d; x++, b += b)
        k&b || (
            t += s*m[x] *(k+b+1==1<<d? 1: D(  m + d, d, k + b)), s = -s
        );
    return t;
}

double m[36],d, *t = m + 6, w[6], s[3], a, b, c;
i,u,h;
main()
{
    for (; i++ < 5; )
    {
        scanf("%lf%lf", &a, &b);
        *t++ = a*a, *t++ = a*b, *t++ = b*b, *t++ = a, *t++ = b, *t++ = 1;
    }
    for (u = 4; u; u /= 2)
    {
        m[0] = u & 1, m[1] = u & 2, m[2] = u & 4;
        d = D(m, 6, 0);
        if (d) 
            for (h = 0; h < 3; h++)
            {
                for (i = 0; i < 6; i++)
                    w[i] = m[i * 6 + h],
                    m[i * 6 + h] = i ? 0 : u;
                s[h] = D(m, 6, 0)/d;
                for (; i--; )
                    m[i * 6 + h] = w[i];
            }
    }
    a = s[0], b = s[1], c = s[2];
    d = b*b - 4 * a * c;
    puts(d ? d < 0 ? !b&(c == a) ? "Circle" : "Ellipse" : "Hyperbola" : "Parabola");
}
edc65
fuente
1

Sabio, 247 bytes

def f(p):
 for i in[1,2,4]:
  z=[i&1,i&2,i&4,0,0,0]
  M=matrix([z]+[[x*x,x*y,y*y,x,y,1]for x,y in p])
  try:A,B,C=(M\vector(z))[:3]
  except:continue
  d=B*B-4*A*C
  return['parabola','hyperbola','circle','ellipse'][[d==0,d>0,d<0and B==0and A==C,d<0].index(1)]

Pruébalo en línea

Esta función toma un iterable de (x,y)pares como entrada, intenta calcular el discriminante de cada uno de los 3 sistemas lineales posibles ( A=1, B=1y C=1), y emite el tipo de sección cónica sobre la base de los valores de la discriminante, A, B, y C.

Probablemente hay más golf por hacer, pero estoy oxidado con Sage y tengo sueño en este momento, así que trabajaré más en él por la mañana.

Mego
fuente