// CERC 2012 // Problem I: The Dragon and the knights // Slow solution (compare every pair of points against every line), O(nm^2) // Author: Grzegorz Herman #include #include #include #include #include using namespace std; struct point { long long x, y; }; struct line { long long a, b, c; }; inline long long operator*(line const & l, point const & p) { return l.a*p.x + l.b*p.y + l.c; } inline bool operator<(line const & l1, line const & l2) { return l1.a*l2.b < l2.a*l1.b; } typedef pair code; void set(code & c, int i) { if (i<64) c.first += (1ULL << i); else c.second += (1ULL << (i-64)); } #define debug(...) fprintf(stderr, __VA_ARGS__) int main() { int nT; scanf("%d", &nT); for (int t=0; t 0) ^ (L[l]*P[q] > 0)) { dif = true; break; } if (!dif) { fresh = false; break; } } if (fresh) guarded++; } // calculate total regions sort(L, L+nL); int total = 2; int added = 0; for (int l=1; l