/** * ICPC Central Europe Regional Contest 2018 * Problem Solution: Mirrority Report * * @author Josef Cibulka */ #include #include #include #include #include #include #include #include #define EPS 1E-9 #define MINDST 1E-7 #define MINASSERT 1.2E-4 using namespace std; typedef long double ld; struct Point { ld x = 0; ld y = 0; bool good = true; Point() { } explicit Point(bool good_) : good(good_) { } Point(ld x_, ld y_) : x(x_), y(y_) { } Point operator+(const Point &rhs) const { return Point (x + rhs.x, y + rhs.y); } Point operator-(const Point& rhs) const { return Point (x - rhs.x, y - rhs.y); } Point operator*(double coeff) const { return Point (coeff * x, coeff * y); } double len() const // Length when considered as a vector. { return sqrt(x*x + y*y); } double dot(const Point &rhs) const // Dot product. { return x * rhs.x + y * rhs.y; } friend ostream& operator<<(ostream &os, const Point &p) { if(!p.good) os << "Bad point."; else os << '(' << p.x << ',' << p.y << ')'; return os; } }; struct Line { Point p, q; int id; // False if vertical, otherwise x + cy = d; bool coeffs (ld &a, ld &b) const { if(abs(q.x - p.x) < EPS) return false; a = (p.y - q.y) / (p.x - q.x); b = p.y - a * p.x; return true; } bool contains (const Point &r) const { Point d1 = r - p; if(abs(d1.x) < EPS && abs(d1.y) < EPS) return true; Point d2 = r - q; return (abs(d1.x * d2.y - d2.x * d1.y) < EPS); } friend ostream& operator<<(ostream& os, const Line &l) { os << "Line: (" << l.p << ',' << l.q << ')'; return os; } }; Point pstart; Point pend; int size; // Intersection or bad point. Lines k and l are not allowed to be identical. Point intersect (Line k, Line l) { ld ka, kb, la, lb; bool kvert = !(k.coeffs(ka, kb)); bool lvert = !(l.coeffs(la, lb)); if(kvert && lvert) return Point(false); if(kvert) { ld x = k.p.x; return Point(x, la * x + lb); } if(lvert) { ld x = l.p.x; return Point(x, ka * x + kb); } if (abs(ka - la) < EPS) return Point(false); ld resx = (kb - lb) / (la - ka); ld resy = la * resx + lb; return Point(resx, resy); } Point mirror (const Line &l, const Point &p) { if(l.contains(p)) return p; Point lvec = l.p - l.q; Point orthovec(lvec.y, -lvec.x); Line pline = Line { p, p+orthovec }; Point inters = intersect(l, pline); assert(inters.good); return p + (inters - p) * 2; } // True iff mid is between a and b. The points a,b,mid are expected to be // collinear. bool between (const Point &a, const Point &b, const Point &mid) { if(abs(a.x-b.x) < EPS) { if(a.y > b.y) return (mid.y >= b.y && mid.y <= a.y); else return (mid.y >= a.y && mid.y <= b.y); } if(a.x > b.x) return (mid.x >= b.x && mid.x <= a.x); else return (mid.x >= a.x && mid.x <= b.x); } bool verify (vector> lines, vector mirrors) { Point pendm = pend; for(const Line &m : mirrors) pendm = mirror(m,pendm); Line ballpath { pstart, pendm }; vector pathpts; pathpts.push_back(pstart); for (const Line &m : mirrors) { Point tmppt = intersect(m, ballpath); if(!tmppt.good) return false; pathpts.push_back(tmppt); } pathpts.push_back(pendm); assert(pathpts.size() == lines.size() + 1); int layercnt = lines.size(); // Verify that mirrors are hit in the correct order. for (size_t i = 1; i < pathpts.size() - 1; ++i) { if(!between(pathpts[i-1], pathpts[i+1], pathpts[i])) { return false; } } for (int i = 0; i < layercnt; ++i) { // Verify that no other mirror is hit between i-th and i+1-st hit. for(const Line &lline : lines[i]) { if(i != layercnt - 1 && lline.id == mirrors[i].id) continue; Point crpt = intersect(lline, ballpath); if(!crpt.good) continue; if(between(pathpts[i], pathpts[i+1], crpt)) { return false; } if(i != layercnt - 1) { Point corner = intersect(lline, mirrors[i]); if(corner.good && (pathpts[i+1] - corner).len() < MINDST) { return false; } assert(!(corner.good && (pathpts[i+1] - corner).len() < MINASSERT)); } } } return true; } int bt (vector> lines, vector mirrors) { int ret = 0; if(verify(lines, mirrors)) ++ret; assert(mirrors.size() == lines.size()-1); int depth = mirrors.size(); if (depth == size) return ret; vector remains(size, true); for(Line m : mirrors) remains[m.id] = false; for(int mrr = 0; mrr < size; ++mrr) { if(!remains[mrr]) continue; vector mirrors_new = mirrors; vector> lines_new = lines; Line mrr_line; vector orig_lines; for(const Line &l : lines[depth]) { if(l.id == mrr) mrr_line = l; } mirrors_new.push_back(mrr_line); vector lines_added; for(const Line &l : lines[depth]) { if(l.id == mrr) continue; lines_added.push_back( Line { mirror(mrr_line, l.p), mirror(mrr_line, l.q), l.id } ); } lines_new.push_back(lines_added); ret += bt(lines_new, mirrors_new); } return ret; } int main(void) { ld x1, y1, x2, y2; cin >> size >> x1 >> y1 >> x2 >> y2; pstart = Point(x1, y1); pend = Point(x2, y2); vector lines_orig; for (int i = 0; i < size; ++i) { cin >> x1 >> y1 >> x2 >> y2; Point a (x1, y1); Point b (x2, y2); lines_orig.push_back(Line {a, b, i}); } vector mirrors; vector> lines; lines.push_back(lines_orig); cout << bt(lines, mirrors) << endl; return 0; }