ars.cpp 1.9 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <memory.h>
  4. #include <math.h>
  5. #define Eps 1e-8
  6. #define Equal(a, b) (fabs((a) - (b)) < Eps)
  7. #define MAXN 101
  8. #define MAXM 101
  9. double pos[MAXN][3];
  10. int ord[MAXN];
  11. double a[MAXN * 3][MAXM];
  12. int P, N, M, testID;
  13. bool vis[MAXN * 3], ans1, ans2;
  14. int main() {
  15. int v1, v2, k;
  16. double delta, mul;
  17. freopen("fg.in", "r", stdin);
  18. freopen("fg.out", "w", stdout);
  19. while (scanf("%d%d", &N, &M) && (N || M)) {
  20. P = 0;
  21. for (int i = 0; i < N; i ++) {
  22. scanf("%lf%lf%lf", &pos[i][0], &pos[i][1], &pos[i][2]);
  23. if (!Equal(pos[i][2], 0)) {
  24. ord[i] = P;
  25. P += 3;
  26. } else ord[i] = -1;
  27. }
  28. memset(a, 0, sizeof(a));
  29. for (int i = 0; i < M; i ++) {
  30. scanf("%d%d", &v1, &v2);
  31. v1 --; v2 --;
  32. for (int j = 0; j < 3; j ++) {
  33. delta = pos[v1][j] - pos[v2][j];
  34. if (ord[v1] != -1) {
  35. a[ord[v1] + j][i] = delta;
  36. }
  37. if (ord[v2] != -1) {
  38. a[ord[v2] + j][i] = -delta;
  39. }
  40. }
  41. }
  42. for (int i = 0; i < P / 3; i ++) {
  43. a[i * 3 + 2][M] = 1;
  44. }
  45. memset(vis, 0, sizeof(vis));
  46. for (int i = 0; i < M; i ++) {
  47. k = -1;
  48. for (int j = 0; j < P; j ++) {
  49. if (!vis[j] && !Equal(a[j][i], 0)) {
  50. k = j;
  51. break;
  52. }
  53. }
  54. if (k == -1) continue;
  55. vis[k] = true;
  56. for (int j = 0; j < P; j ++) if (j != k && !Equal(a[j][i], 0)) {
  57. mul = a[j][i] / a[k][i];
  58. for (int w = i; w <= M; w ++) {
  59. a[j][w] -= a[k][w] * mul;
  60. }
  61. }
  62. }
  63. ans1 = true;
  64. ans2 = false;
  65. for (int i = 0; i < P; i ++) if (!vis[i]) {
  66. if (!Equal(a[i][M], 0)) {
  67. ans1 = false;
  68. break;
  69. } else {
  70. ans2 = true;
  71. }
  72. }
  73. printf("Sculpture %d: ", ++ testID);
  74. if (!ans1) printf("NON-STATIC\n");
  75. else if (ans2) printf("UNSTABLE\n");
  76. else printf("STABLE\n");
  77. }
  78. return 0;
  79. }