#include #include #include #include #include #include #include using namespace std; #define FOR(i,a,b) for (int i = (a); i < (b); ++i) struct Vector { int x, y; Vector(): x(0), y(0) { } Vector(int xx, int yy): x(xx), y(yy) { } Vector operator+(const Vector & v) const { return Vector(x + v.x, y + v.y); } Vector operator-(const Vector & v) const { return Vector(x - v.x, y - v.y); } }; inline int cross_product(const Vector & v1, const Vector & v2) { return v1.x * v2.y - v1.y * v2.x; } inline int dir(const Vector & seg1, const Vector & seg2, const Vector & point) { return cross_product(seg2 - seg1, point - seg1); } bool between(int a, int b, int c) { return min(a, b) <= c && c <= max(a,b); } bool on_segment(const Vector & s1, const Vector & s2, const Vector & point) { return between(s1.x, s2.x, point.x) && between(s1.y, s2.y, point.y); } bool intersect(const Vector & s1, const Vector & s2, const Vector & s3, const Vector & s4) { int d1 = dir(s1, s2, s3), d2 = dir(s1, s2, s4), d3 = dir(s3, s4, s1), d4 = dir(s3, s4, s2); if (((d1 < 0 && d2 > 0) || (d1 > 0 && d2 < 0)) && ((d3 < 0 && d4 > 0) || (d3 > 0 && d4 < 0))) return true; if (!d1 && on_segment(s1, s2, s3)) return true; if (!d2 && on_segment(s1, s2, s4)) return true; if (!d3 && on_segment(s3, s4, s1)) return true; if (!d4 && on_segment(s3, s4, s2)) return true; return false; } struct rec { char name; vector points; vector inter; bool operator<(const rec & r) const { return name < r.name; } }; void read(int shape, vector & points) { if (shape == 0) { int x1, y1, x2, y2; scanf("(%d,%d) (%d,%d) ", &x1, &y1, &x2, &y2); x1 *= 2; y1 *= 2; x2 *= 2; y2 *= 2; int x3 = (x1 + x2), y3 = (y1 + y2); points.push_back(Vector(x1,y1)); points.push_back(Vector((x3+y2-y1)/2, (y3+x1-x2)/2)); points.push_back(Vector(x2, y2)); points.push_back(Vector((x3-y2+y1)/2, (y3-x1+x2)/2)); } if (shape == 1) { int x1, y1, x2, y2, x3, y3; scanf("(%d,%d) (%d,%d) (%d,%d) ", &x1, &y1, &x2, &y2, &x3, &y3); x1 *= 2; y1 *= 2; x2 *= 2; y2 *= 2; x3 *= 2; y3 *= 2; points.push_back(Vector(x1, y1)); points.push_back(Vector(x2, y2)); points.push_back(Vector(x3, y3)); points.push_back(Vector(x1 + x3 - x2, y1 + y3 - y2)); } if (shape == 2) { int x1, y1, x2, y2; scanf("(%d,%d) (%d,%d) ", &x1, &y1, &x2, &y2); x1 *= 2; y1 *= 2; x2 *= 2; y2 *= 2; points.push_back(Vector(x1, y1)); points.push_back(Vector(x2, y2)); } if (shape == 3) { int x1, y1, x2, y2, x3, y3; scanf("(%d,%d) (%d,%d) (%d,%d) ", &x1, &y1, &x2, &y2, &x3, &y3); x1 *= 2; y1 *= 2; x2 *= 2; y2 *= 2; x3 *= 2; y3 *= 2; points.push_back(Vector(x1, y1)); points.push_back(Vector(x2, y2)); points.push_back(Vector(x3, y3)); } if (shape == 4) { int N; scanf("%d ", &N); int x1, y1; FOR(i, 0, N) { scanf("(%d,%d) ", &x1, &y1); x1 *= 2; y1 *= 2; points.push_back(Vector(x1, y1)); } } } string sq("square"), rc("rectangle"), li("line"), tr("triangle"), po("polygon"); int sh(const string & str) { if (str == sq) return 0; if (str == rc) return 1; if (str == li) return 2; if (str == tr) return 3; if (str == po) return 4; cout << "CHYBA" << endl; } int main() { char temp[100]; while(1) { vector shapes; bool end = false; while (1) { char c; scanf("%c ", &c); if (c == '.') { end = true; break; } if (c == '-') break; scanf("%s ", temp); rec rr; rr.name = c; read(sh(temp), rr.points); shapes.push_back(rr); } if (end) break; FOR(i, 0, shapes.size()) shapes[i].points.push_back(shapes[i].points[0]); FOR(i, 0, shapes.size()) FOR(j, i+1, shapes.size()) { bool found = false; FOR(k, 0, shapes[i].points.size()-1) { FOR(l, 0, shapes[j].points.size()-1) if (intersect(shapes[i].points[k], shapes[i].points[k+1], shapes[j].points[l], shapes[j].points[l+1])) { found = true; break; } if (found) break; } if (found) { shapes[i].inter.push_back(shapes[j].name); shapes[j].inter.push_back(shapes[i].name); } } sort(shapes.begin(), shapes.end()); FOR(i, 0, shapes.size()) { sort(shapes[i].inter.begin(), shapes[i].inter.end()); if (shapes[i].inter.size() == 0) printf("%c has no intersections\n", shapes[i].name); else { printf("%c intersects with %c", shapes[i].name, shapes[i].inter[0]); FOR(j, 1, shapes[i].inter.size()) { if (j + 1 == shapes[i].inter.size()) printf(" and "); else printf(", "); printf("%c", shapes[i].inter[j]); } printf("\n"); } } printf("\n"); } return 0; }