#include #include #include #include #include #include using namespace std; #define EPSILON 1E-6 void transl(string a, int &x, int &y) { sscanf(a.c_str(), "(%d,%d)", &x, &y); } class line { public: int x1, y1, x2, y2; void parse(string a, string b) { sscanf(a.c_str(), "(%d,%d)", &x1, &y1); sscanf(b.c_str(), "(%d,%d)", &x2, &y2); } }; bool insect(line &a, line &b) { double bax = a.x2 - a.x1; double bay = a.y2 - a.y1; double cdx = b.x1 - b.x2; double cdy = b.y1 = b.y2; double cax = b.x1 - a.x1; double cay = b.y1 - a.y1; double d = (bax*cdy - bay*cdx); if (fabs(d) < EPSILON) return false; double t1 = (cax*cdy - cay*cdx)/d; double t2 = (bax*cay - bay*cdy)/d; if (t1 < -EPSILON || t1 > 1.0 + EPSILON || t2 < -EPSILON || t2 > 1.0 + EPSILON) return false; return true; } class utvar { public: bool def; vector lajny; void add(line &l) { lajny.push_back(l); def = true; } void add(int x1, int y1, int x2, int y2) { line l; l.x1 = x1; l.y1 = y1; l.x2 = x2; l.y2 = y2; add(l); } void clear() { def = false; lajny.clear(); } utvar() { clear(); } }; bool insect(utvar &a, utvar &b) { for (vector::iterator i = a.lajny.begin(); i != a.lajny.end(); ++i) { for (vector::iterator j = b.lajny.begin(); j != b.lajny.end(); ++j) { if (insect(*i, *j)) return true; } } return false; } int readline(utvar *x) { char c; string tvar; string sour, sour1; int poc; cin >> c; if (c == '.') return -2; if (c < 'A' || c > 'Z') return -1; int i = c - 'A'; cin >> tvar; if (tvar == "square") { string a, b; cin >> a; cin >> b; line l; l.parse(a, b); int x1, x2, y1, y2; x1 = l.x1; y1 = l.y1; x2 = l.x2; y2 = l.y2; int Sx = (x1+x2); int Sy = (y1+y2); int vx = (x2-x1); int vy = (y2-y1); x[i].add( (Sx+vx)/2, (Sy+vy)/2, (Sx-vy)/2, (Sy+vx)/2 ); x[i].add( (Sx-vy)/2, (Sy+vx)/2, (Sx-vx)/2, (Sy-vy)/2 ); x[i].add( (Sx-vx)/2, (Sy-vy)/2, (Sx+vy)/2, (Sy-vx)/2 ); x[i].add( (Sx+vy)/2, (Sy-vx)/2, (Sx+vx)/2, (Sy+vy)/2 ); return 1; } if (tvar == "line") { string a, b; cin >> a; cin >> b; line l; l.parse(a, b); x[i].add(l); return 1; } if (tvar == "rectangle") { string a, b, c; cin >> a; cin >> b; cin >> c; int x1, x2, x3, x4, y1, y2, y3, y4; transl(a, x1, y1); transl(b, x2, y2); transl(c, x3, y3); x4 = x3 - ( (x2 - x1) ); y4 = y3 - ( (y2 - y1) ); x[i].add(x1, y1, x2, y2); x[i].add(x2, y2, x3, y3); x[i].add(x3, y3, x4, y4); x[i].add(x4, y4, x1, y1); return 1; } if (tvar == "triangle") poc = 3; if (tvar == "polygon") { cin >> poc; } int x1, y1, x2, y2; cin >> sour1; transl(sour1, x1, y1); for (int bla = 1; bla < poc; bla++) { cin >> sour; transl(sour, x2, y2); x[i].add(x1, y1, x2, y2); x1 = x2; y1 = y2; } transl(sour1, x2, y2); x[i].add(x1, y1, x2, y2); return 1; } #define MAX 26 int main() { utvar x[MAX]; bool is[MAX*MAX]; int count[MAX]; bool cont = true; while (cont) { for (int i = 0; i < MAX; i++) x[i].clear(); for (int i = 0; i < MAX*MAX; i++) is[i] = false; for (int i = 0; i < MAX; i++) count[i] = 0; cont = false; while (readline(x) > 0) { cont = true; } if (!cont) break; for (int i = 0; i < MAX; i++) { if (!x[i].def) continue; for (int j = i+1; j < MAX; j++) { if (!x[j].def) continue; if (insect(x[i], x[j])) { is[i+MAX*j] = true; is[j+MAX*i] = true; count[i]++; count[j]++; } } } for (int i = 0; i < MAX; i++) { if (!x[i].def) continue; if (count[i] == 0) { cout << (char) ('A'+i) << " has no intersections" << endl; } else if (count[i] == 1) { for (int j = 0; j < MAX; j++) { if (is[j+i*MAX]) { cout << (char)('A'+i) << " intersects with " << (char)('A'+j) << endl; break; } } } else if (count[i] == 2) { cout << (char)('A'+i) << " intersects with "; for (int j = 0; j < MAX; j++) { if (i == j) continue; if (is[j+i*MAX]) { count[i]--; if (count[i] == 0) { cout << " and " << (char)('A'+j) << endl; break; } else { cout << (char)('A'+j); } } } } else { cout << (char)('A'+i) << " intersects with "; for (int j = 0; j < MAX; j++) { if (i == j) continue; if (is[j+i*MAX]) { count[i]--; if (count[i] == 0) { cout << "and " << (char)('A'+j) << endl; break; } else { cout << (char)('A'+j) << ", "; } } } } } cout << endl; } return 0; }