uppga.c (3592B)
1 #include "common.h" 2 3 static int inint(fmpq_t x, fmpq_t min, fmpq_t max) { 4 return (fmpq_cmp(min, x) <= 0) && (fmpq_cmp(x, max) <= 0); 5 } 6 7 static int online_segm(pt_t *a, pt_t *adir, fmpq_t min, fmpq_t max, pt_t bt) { 8 int ret = 0; 9 10 fmpq_t t; 11 fmpq_init(t); 12 13 fmpq_sub(t, bt.c[0], a->c[0]); 14 fmpq_div(t, t, adir->c[0]); 15 16 if (inint(t, min, max)) { 17 fmpq_mul(t, t, adir->c[1]); 18 fmpq_add(t, t, a->c[1]); 19 if (fmpq_cmp(bt.c[1], t) == 0) { 20 ret = 1; 21 } 22 } 23 24 fmpq_clear(t); 25 return ret; 26 } 27 28 static int para(pt_t *a, pt_t *adir, pt_t *b, pt_t *bdir, fmpq_t min, 29 fmpq_t max) { 30 int r = 0; 31 pt_t bt; 32 fmpq_init(bt.c[0]); 33 fmpq_init(bt.c[1]); 34 fmpq_init(bt.c[2]); 35 36 fmpq_mul(bt.c[0], bdir->c[0], min); 37 fmpq_add(bt.c[0], bt.c[0], b->c[0]); 38 fmpq_mul(bt.c[1], bdir->c[1], min); 39 fmpq_add(bt.c[1], bt.c[1], b->c[1]); 40 fmpq_mul(bt.c[2], bdir->c[2], min); 41 fmpq_add(bt.c[2], bt.c[2], b->c[2]); 42 43 if (online_segm(a, adir, min, max, bt)) { 44 r = 1; 45 } 46 47 fmpq_mul(bt.c[0], bdir->c[0], max); 48 fmpq_add(bt.c[0], bt.c[0], b->c[0]); 49 fmpq_mul(bt.c[1], bdir->c[1], max); 50 fmpq_add(bt.c[1], bt.c[1], b->c[1]); 51 fmpq_mul(bt.c[2], bdir->c[2], max); 52 fmpq_add(bt.c[2], bt.c[2], b->c[2]); 53 54 if (r == 0 && online_segm(a, adir, min, max, bt)) { 55 r = 2; 56 } 57 58 fmpq_mul(bt.c[0], adir->c[0], max); 59 fmpq_add(bt.c[0], bt.c[0], a->c[0]); 60 fmpq_mul(bt.c[1], adir->c[1], max); 61 fmpq_add(bt.c[1], bt.c[1], a->c[1]); 62 fmpq_mul(bt.c[2], adir->c[2], max); 63 fmpq_add(bt.c[2], bt.c[2], a->c[2]); 64 65 if (r == 0 && online_segm(b, bdir, min, max, bt)) { 66 r = 3; 67 } 68 69 fmpq_clear(bt.c[0]); 70 fmpq_clear(bt.c[1]); 71 fmpq_clear(bt.c[2]); 72 73 return r; 74 } 75 76 static int has_solution_in(pt_t *a, pt_t *adir, pt_t *b, pt_t *bdir, fmpq_t min, 77 fmpq_t max) { 78 int r = 0; 79 fmpq_mat_t A, Ainv, B, x; 80 fmpq_t is[2]; 81 82 fmpq_mat_init(A, 2, 2); 83 fmpq_mat_init(B, 2, 1); 84 fmpq_mat_init(x, 2, 1); 85 fmpq_mat_init(Ainv, 2, 2); 86 fmpq_init(is[0]); 87 fmpq_init(is[1]); 88 89 fmpq_set(fmpq_mat_entry(A, 0, 0), bdir->c[0]); 90 fmpq_set(fmpq_mat_entry(A, 0, 1), adir->c[0]); 91 fmpq_set(fmpq_mat_entry(A, 1, 0), bdir->c[1]); 92 fmpq_set(fmpq_mat_entry(A, 1, 1), adir->c[1]); 93 fmpq_sub(fmpq_mat_entry(B, 0, 0), a->c[0], b->c[0]); 94 fmpq_sub(fmpq_mat_entry(B, 1, 0), a->c[1], b->c[1]); 95 96 if (fmpq_mat_inv(Ainv, A) != 0) { 97 fmpq_mat_mul(x, Ainv, B); 98 if (!(fmpq_cmp_ui(fmpq_mat_entry(x, 0, 0), 0) < 0) && 99 !(fmpq_cmp_ui(fmpq_mat_entry(x, 1, 0), 0) > 0)) { 100 fmpq_mul(is[0], bdir->c[0], fmpq_mat_entry(x, 0, 0)); 101 fmpq_add(is[0], is[0], b->c[0]); 102 103 fmpq_mul(is[1], bdir->c[1], fmpq_mat_entry(x, 0, 0)); 104 fmpq_add(is[1], is[1], b->c[1]); 105 106 if (inint(is[0], min, max) && inint(is[1], min, max)) { 107 r = 1; 108 } 109 } 110 } else { 111 r = para(a, adir, b, bdir, min, max); 112 } 113 114 fmpq_mat_clear(A); 115 fmpq_mat_clear(Ainv); 116 fmpq_mat_clear(B); 117 fmpq_mat_clear(x); 118 fmpq_clear(is[0]); 119 fmpq_clear(is[1]); 120 121 return r; 122 } 123 124 int main(int argc, char **argv) { 125 char **lines; 126 size_t nlines = readlines(&lines, "input"); 127 128 pt_t pts[nlines], dir[nlines]; 129 read_pts(pts, dir, lines, nlines); 130 131 size_t i, j; 132 133 fmpq_t min, max; 134 fmpq_init(min); 135 fmpq_init(max); 136 fmpq_set_ui(min, 200000000000000ULL, 1); 137 fmpq_set_ui(max, 400000000000000ULL, 1); 138 139 size_t count = 0; 140 for (i = 0; i < nlines; i++) { 141 for (j = i + 1; j < nlines; j++) { 142 if (has_solution_in(&pts[i], &dir[i], &pts[j], &dir[j], min, max)) { 143 count++; 144 } 145 } 146 } 147 148 fmpq_clear(min); 149 fmpq_clear(max); 150 151 printf("%lld\n", count); 152 }