71. Recuento de subconjuntos automáticos
Autor: Pablo Ariel Heiber
Limite de tiempo : 1 seg. Total runs : 1 Aceptados : 0
Un conjunto de puntos en el plano gira automáticamente si hay un punto P , el centro y un ángulo α ,expresado en grados, donde 0 < α < 360, de modo que la rotación del plano, con el centro P y ángulo α, asigna todos los puntos del conjunto a algún punto también en el conjunto.
Te dan un conjunto de N puntos distintos, todos con coordenadas enteras . Encuentre el número de subconjuntos distintos de tamaño 1, 2,. . . , N que son auto giratorios. Dos subconjuntos se consideran distintos si uno contiene un punto que el otro no contiene.
Entrada
La primera línea de la entrada contiene un número entero N que representa el número de puntos en el conjunto de entrada (1 ≤ N ≤ 1000). Cada una de las siguientes N líneas describe un punto diferente del conjunto y contiene dos enteros X e Y que dan sus coordenadas en un sistema de coordenadas cartesianas (−10 9 ≤ X, Y ≤ 10 9 ). Todos los puntos en el conjunto de entrada son distintos.
Salida
Salida de una sola línea que contiene N enteros S 1 , S 2 ,. . . , S N . Para i = 1, 2,. . . , N el entero S i debe ser el número de subconjuntos de i puntos del conjunto de entrada que se auto rotan. Dado que estos números pueden ser muy grandes, envíeles el módulo 10 9 + 7.
Ejemplo Entrada
3
1 1
2 2
1 0
7
-2 0
-1 1
0 2
0 0
2 0
1 -1
0 -2
1
-1000000000 1000000000
Ejemplo Salida
3 3 0
7 21 5 5 3 1 1
1