【input】Z line (1933,2413) (2607,388)A square (2434,925) (2065,1534)R polygon 5 (1251,2398) (-1319,-569) (1964,-1947) (1705,2845) (-994,-551)V line (2689,2103) (-1350,457)P line (-121,-709) (-937,1486)S rectangle (377,-24) (441,-258) (1845,-642)B triangle (-1820,1247) (566,964) (1564,1972)T line (-670,2470) (-395,1531)L triangle (-1466,969) (-239,1757) (2848,2404)M rectangle (-242,202) (63,-413) (3753,-2243)N line (-1507,42) (-1804,1740)O square (304,-715) (534,1418)C line (-1977,499) (1868,83)Q square (-1804,-210) (-315,2600)-D line (-1336,-714) (-1702,308)K line (2153,1486) (-138,893)H square (-450,-1268) (-1739,2968)C rectangle (-157,-301) (337,278) (-1400,-1204)M line (1374,1711) (-1074,2984)W rectangle (149,221) (-361,-191) (463,829)T square (651,-980) (707,1451)Z rectangle (35,-140) (429,-265) (679,-1053)E line (2167,2402) (-1630,-807)A rectangle (-243,-493) (-419,191) (-2471,719)F rectangle (136,-109) (429,-59) (329,-645)G line (1912,1384) (560,2522)I triangle (803,-1493) (1250,428) (-1355,1769)Q line (-686,1911) (2760,1923)N line (967,-1234) (-77,2731)-Q polygon 7 (19,407) (-146,774) (74,1867) (2970,2297) (165,-1021) (-1567,-1801) (-1099,443)A rectangle (-243,-183) (-312,-2) (-674,136)K triangle (-695,1986) (905,-1405) (-211,-1490)J square (530,1487) (118,-1696)X square (-374,-790) (2502,1957)S line (2859,-1561) (2557,2955)E rectangle (-5,-305) (-147,-251) (-363,317)O triangle (-625,-1042) (1377,-115) (37,1641)F rectangle (259,-429) (289,-404) (139,-584)-W square (996,-1997) (2218,2787)X polygon 3 (787,1020) (-969,-1508) (2270,2500)T square (-1125,-187) (-1414,2113)K square (2880,-1273) (2986,304)E rectangle (205,368) (236,212) (1016,57)Y square (-1996,-1348) (-1545,1840)V polygon 10 (-543,1468) (1328,2443) (2619,806) (2353,1091) (2447,570) (2837,-1825) (-1857,-1586) (-331,625) (-1113,-1502) (197,574)Z polygon 8 (-156,1249) (-133,1674) (-1392,1042) (2105,-957) (2912,1975) (1195,2697) (1082,-64) (1081,681)B polygon 11 (2391,-1682) (2569,1841) (2316,804) (1625,92) (823,1035) (612,1308) (-1664,2716) (-1363,-460) (1971,-1782) (-1194,35) (-699,573)A rectangle (-371,-235) (9,363) (-3579,-1917)U rectangle (307,-40) (-159,-500) (2141,1830)H triangle (-780,2320) (1012,-1816) (1980,1349)C square (-759,1872) (2836,1399)D rectangle (472,83) (78,-46) (723,1924)F square (-384,229) (736,-577)G rectangle (-77,317) (426,-100) (1260,-1106)Q triangle (-778,579) (-1534,474) (196,-293)S square (-1893,-690) (2521,431)R line (1885,-1907) (2891,-1798)I square (2291,2484) (2162,-1280)J line (2999,1660) (721,1597)L triangle (-824,-757) (769,1373) (950,-180)M rectangle (-370,-221) (341,-125) (53,-2258)-Q polygon 12 (-242,643) (447,350) (-1396,1043) (-1264,126) (-473,-963) (2475,-1568) (1870,-1091) (1190,50) (669,2183) (1776,1305) (833,2334) (-676,1920)X line (-383,836) (592,155)K square (2799,-129) (1052,-245)Y polygon 4 (2145,-823) (2708,2578) (-1952,-1383) (2120,98)Z polygon 13 (2098,-1112) (2036,-1014) (1174,-1851) (640,-1658) (739,-725) (-700,-1844) (-629,-1083) (596,1095) (-94,-207) (94,-1100) (1594,1569) (1604,-528) (2158,149)C polygon 9 (144,2825) (-1637,857) (502,292) (-463,-1422) (1411,-1399) (2525,-304) (2444,2672) (1494,2284) (1832,2775)F polygon 7 (2935,828) (1354,2770) (-1218,94) (2482,1107) (841,855) (-17,908) (1532,1742)A square (835,-944) (1100,2163)U polygon 11 (1460,964) (1461,2840) (328,1658) (-70,876) (295,1377) (1366,2643) (-274,123) (-492,789) (833,2817) (-1407,395) (-1889,-733)G rectangle (214,146) (-195,62) (225,2107)D polygon 9 (754,-1107) (-1781,48) (569,1700) (1268,2019) (1862,724) (2589,-1323) (1157,1865) (1282,-178) (422,254)-P polygon 11 (-728,2666) (1962,2817) (1123,291) (235,1939) (1372,-477) (-1133,-689) (-1054,-1382) (-521,-1179) (522,-1582) (-1935,-1361) (318,845)O triangle (2168,1629) (1926,1507) (1645,2840)G rectangle (358,132) (-414,-167) (184,1377)M square (-353,-803) (-509,2311)K line (-1210,965) (-1016,-792)E triangle (2878,1579) (2969,-1407) (748,2950)X square (1596,-1289) (1278,2865)-E square (-98,-814) (-1374,527)X polygon 5 (598,-184) (-1979,-302) (-234,-1108) (2306,-1638) (-397,1936)O rectangle (-302,384) (-73,236) (667,-909)M square (685,-1324) (-878,-347)I polygon 12 (1328,150) (492,-1801) (1774,-101) (2613,1777) (545,1108) (-765,1653) (25,2299) (-1428,2967) (-1014,272) (-1412,28) (2149,1361) (-345,-1171)C square (-699,-1701) (-1564,415)D line (2565,-666) (-1685,1340)N polygon 12 (2824,1092) (1730,392) (1820,1654) (853,1092) (-957,1834) (1520,-1461) (-600,-623) (-97,-960) (-1933,-1920) (-1841,2538) (2656,1754) (2737,1410)P line (1752,-1990) (-1944,-1653)Y triangle (2792,-1185) (1624,2964) (-1179,-523)-U polygon 11 (2042,1312) (480,913) (2225,633) (646,-843) (357,-278) (-988,1486) (-1622,-1297) (-1890,2941) (-1055,2398) (2353,2712) (-360,1116)O square (-1014,323) (293,-1208)B triangle (529,-411) (-1412,-1990) (2503,2813)H line (322,-648) (-1776,1334)E rectangle (-110,-199) (395,-165) (259,-2185)Q rectangle (-161,-135) (-231,-411) (321,-271)P rectangle (-5,-360) (-491,-476) (-143,982)-O square (2411,-1619) (-562,1085)I square (-580,924) (1616,-190)X polygon 4 (2110,-857) (-1269,1251) (-1848,-1245) (-315,-898)U square (-135,1875) (412,2950)Z triangle (-630,-762) (2043,2532) (-185,259)Y rectangle (223,-223) (264,-244) (348,-408)-G triangle (2020,-1129) (156,2172) (978,-1807)C square (2815,1491) (-1652,228)O rectangle (155,-336) (47,-450) (275,-234)J rectangle (-70,-341) (-116,208) (-1214,300)K polygon 11 (-1731,557) (1333,-1555) (1420,-157) (77,-539) (98,932) (2645,998) (2884,2095) (2491,-958) (1492,-1027) (1294,-1742) (-1399,-556)H square (-1742,-1851) (1394,780)Z triangle (775,1442) (-521,460) (1887,-749)D rectangle (212,-98) (-252,209) (-559,673)R rectangle (-256,27) (148,69) (-104,-2355)W triangle (1617,2635) (542,1875) (2785,-1064)A triangle (2858,-1217) (2104,-663) (1243,991)U square (-1692,-348) (-1698,-92)L square (41,2517) (2946,-1079)T square (1094,2127) (37,-288)X rectangle (87,-248) (368,95) (-661,-748)M triangle (2666,2416) (1974,2009) (1356,873)B line (1175,578) (1074,2230)F rectangle (28,392) (313,-104) (2297,-1244)I polygon 6 (-1403,-1004) (-548,-1972) (-10,-651) (2168,-1142) (1268,2669) (902,2117)N triangle (2586,116) (329,1299) (2801,1527)Y square (511,1750) (-1539,-1789)P polygon 8 (887,1982) (-1247,2002) (-1879,-1626) (2562,-145) (-346,-131) (2295,194) (-377,460) (2244,2935)Q square (1719,975) (1858,-1099)E square (2468,-1370) (2817,1254)S square (1221,2873) (-1496,-1673)V triangle (-1299,2790) (1833,1707) (1012,1128)-.【output】A intersects with ZB intersects with L, N, O, P, Q, R, T, and VC intersects with N, O, P, Q, and RL intersects with B, P, Q, R, T, and ZM intersects with O, R, and SN intersects with B and CO intersects with B, C, M, P, Q, R, S, and VP intersects with B, C, L, O, Q, R, and VQ intersects with B, C, L, O, P, R, and VR intersects with B, C, L, M, O, P, Q, and VS intersects with M and OT intersects with B and LV intersects with B, O, P, Q, R, and ZZ intersects with A, L, and VA intersects with C, D, E, T, and WC intersects with A, H, I, and TD intersects with A and EE intersects with A, D, G, H, I, K, M, N, Q, and TF intersects with H, I, T, and ZG intersects with E, K, and QH intersects with C, E, F, I, K, N, Q, T, W, and ZI intersects with C, E, F, H, K, N, T, W, and ZK intersects with E, G, H, I, N, T, and WM intersects with E, N, and QN intersects with E, H, I, K, M, Q, T, and WQ intersects with E, G, H, M, and NT intersects with A, C, E, F, H, I, K, N, W, and ZW intersects with A, H, I, K, N, and TZ intersects with F, H, I, and TA intersects with K, O, and XE intersects with O and XF has no intersectionsJ intersects with K, O, Q, and XK intersects with A, J, O, Q, and XO intersects with A, E, J, K, Q, and XQ intersects with J, K, O, S, and XS intersects with QX intersects with A, E, J, K, O, and QA intersects with B, F, G, L, M, Q, S, V, W, Y, and ZB intersects with A, C, D, F, G, H, I, J, K, L, M, Q, S, T, U, V, W, X, Y, and ZC intersects with B, D, E, F, H, I, J, L, S, T, U, V, W, X, and ZD intersects with B, C, E, F, G, H, I, J, L, S, U, W, X, and ZE intersects with C, D, F, I, L, U, and XF intersects with A, B, C, D, E, G, H, L, M, Q, U, V, W, X, Y, and ZG intersects with A, B, D, F, H, L, M, U, V, X, and ZH intersects with B, C, D, F, G, I, J, L, M, S, T, U, V, W, X, and ZI intersects with B, C, D, E, H, J, K, L, S, U, V, W, X, and ZJ intersects with B, C, D, H, I, U, V, W, X, and ZK intersects with B, I, V, W, and ZL intersects with A, B, C, D, E, F, G, H, I, M, Q, U, V, W, X, Y, and ZM intersects with A, B, F, G, H, L, Q, S, U, V, W, and XQ intersects with A, B, F, L, M, S, T, U, V, W, X, and YR intersects with VS intersects with A, B, C, D, H, I, M, Q, T, U, V, W, X, Y, and ZT intersects with B, C, H, Q, S, V, W, Y, and ZU intersects with B, C, D, E, F, G, H, I, J, L, M, Q, S, V, W, X, and ZV intersects with A, B, C, F, G, H, I, J, K, L, M, Q, R, S, T, U, W, X, Y, and ZW intersects with A, B, C, D, F, H, I, J, K, L, M, Q, S, T, U, V, X, Y, and ZX intersects with B, C, D, E, F, G, H, I, J, L, M, Q, S, U, V, W, and ZY intersects with A, B, F, L, Q, S, T, V, W, and ZZ intersects with A, B, C, D, F, G, H, I, J, K, L, S, T, U, V, W, X, and YA intersects with C, D, F, G, K, Q, U, Y, and ZC intersects with A, D, F, G, K, Q, U, X, Y, and ZD intersects with A, C, F, G, K, Q, U, X, Y, and ZF intersects with A, C, D, G, Q, U, X, Y, and ZG intersects with A, C, D, F, Q, U, X, Y, and ZK intersects with A, C, D, Q, Y, and ZQ intersects with A, C, D, F, G, K, U, X, Y, and ZU intersects with A, C, D, F, G, Q, X, Y, and ZX intersects with C, D, F, G, Q, U, Y, and ZY intersects with A, C, D, F, G, K, Q, U, X, and ZZ intersects with A, C, D, F, G, K, Q, U, X, and YE intersects with O, P, and XG intersects with M, P, and XK intersects with M and PM intersects with G, K, P, and XO intersects with E, P, and XP intersects with E, G, K, M, O, and XX intersects with E, G, M, O, and PC intersects with E, I, M, N, X, and YD intersects with I, N, X, and YE intersects with C, I, M, N, O, X, and YI intersects with C, D, E, M, N, O, X, and YM intersects with C, E, I, N, O, X, and YN intersects with C, D, E, I, M, P, X, and YO intersects with E, I, M, X, and YP intersects with NX intersects with C, D, E, I, M, N, O, and YY intersects with C, D, E, I, M, N, O, and XB intersects with E, H, O, P, Q, and UE intersects with B, H, O, P, Q, and UH intersects with B, E, O, P, Q, and UO intersects with B, E, H, P, Q, and UP intersects with B, E, H, O, Q, and UQ intersects with B, E, H, O, P, and UU intersects with B, E, H, O, P, and QI intersects with O, X, and ZO intersects with I, X, and ZU has no intersectionsX intersects with I, O, and ZY has no intersectionsZ intersects with I, O, and XA intersects with C, E, H, I, K, L, N, P, Q, S, T, and WB intersects with H, K, N, P, T, V, W, and ZC intersects with A, E, F, G, H, I, J, K, L, M, N, P, Q, R, S, V, W, X, Y, and ZD intersects with I, J, K, L, P, R, T, X, and ZE intersects with A, C, F, H, I, K, L, N, P, Q, S, T, W, and ZF intersects with C, E, G, H, I, K, L, O, P, Q, S, T, X, Y, and ZG intersects with C, F, H, I, K, L, N, P, Q, S, T, V, Y, and ZH intersects with A, B, C, E, F, G, I, K, L, N, P, Q, R, S, T, U, W, Y, and ZI intersects with A, C, D, E, F, G, H, J, K, L, M, N, P, Q, R, S, T, V, W, Y, and ZJ intersects with C, D, I, K, L, P, R, T, and XK intersects with A, B, C, D, E, F, G, H, I, J, L, M, N, O, P, Q, R, S, T, W, X, Y, and ZL intersects with A, C, D, E, F, G, H, I, J, K, M, P, Q, R, S, T, V, W, X, Y, and ZM intersects with C, I, K, L, N, S, T, V, and WN intersects with A, B, C, E, G, H, I, K, M, P, Q, S, T, V, W, Y, and ZO intersects with F, K, P, R, and TP intersects with A, B, C, D, E, F, G, H, I, J, K, L, N, O, Q, R, S, T, U, V, W, X, Y, and ZQ intersects with A, C, E, F, G, H, I, K, L, N, P, S, T, W, Y, and ZR intersects with C, D, H, I, J, K, L, O, P, S, T, X, and YS intersects with A, C, E, F, G, H, I, K, L, M, N, P, Q, R, V, W, and YT intersects with A, B, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, V, W, X, Y, and ZU intersects with H and PV intersects with B, C, G, I, L, M, N, P, S, T, W, Y, and ZW intersects with A, B, C, E, H, I, K, L, M, N, P, Q, S, T, and VX intersects with C, D, F, J, K, L, P, R, T, and ZY intersects with C, F, G, H, I, K, L, N, P, Q, R, S, T, V, and ZZ intersects with B, C, D, E, F, G, H, I, K, L, N, P, Q, T, V, X, and Y

#include <iostream>#include <cstdio>#include <cstring>#include <cstdlib>#include <cmath>#include <algorithm>#include <vector>#define pi acos(-1.0)#define eps 1e-8using namespace std;struct Point{    double x,y;    Point(double x=0, double y=0):x(x),y(y) {}    void input() { scanf("%lf%lf",&x,&y); }};typedef Point Vector;struct Line{    Point p;    Vector v;    double ang;    Line(){}    Line(Point p, Vector v):p(p),v(v) { ang = atan2(v.y,v.x); }    Point point(double t) { return Point(p.x + t*v.x, p.y + t*v.y); }    bool operator < (const Line &L)const { return ang < L.ang; }};int dcmp(double x) {    if(x < -eps) return -1;    if(x > eps) return 1;    return 0;}template <class T> T sqr(T x) { return x * x;}Vector operator + (Vector A, Vector B) { return Vector(A.x + B.x, A.y + B.y); }Vector operator - (Vector A, Vector B) { return Vector(A.x - B.x, A.y - B.y); }Vector operator * (Vector A, double p) { return Vector(A.x*p, A.y*p); }Vector operator / (Vector A, double p) { return Vector(A.x/p, A.y/p); }bool operator < (const Point& a, const Point& b) { return a.x < b.x || (a.x == b.x && a.y < b.y); }bool operator >= (const Point& a, const Point& b) { return a.x >= b.x && a.y >= b.y; }bool operator <= (const Point& a, const Point& b) { return a.x <= b.x && a.y <= b.y; }bool operator == (const Point& a, const Point& b) { return dcmp(a.x-b.x) == 0 && dcmp(a.y-b.y) == 0; }double Dot(Vector A, Vector B) { return A.x*B.x + A.y*B.y; }double Length(Vector A) { return sqrt(Dot(A, A)); }double Angle(Vector A, Vector B) { return acos(Dot(A, B) / Length(A) / Length(B)); }double Cross(Vector A, Vector B) { return A.x*B.y - A.y*B.x; }Vector VectorUnit(Vector x){ return x / Length(x);}Vector Normal(Vector x) { return Point(-x.y, x.x) / Length(x);}double angle(Vector v) { return atan2(v.y, v.x); }bool SegmentIntersection(Point A,Point B,Point C,Point D) {    return max(A.x,B.x) >= min(C.x,D.x) &&           max(C.x,D.x) >= min(A.x,B.x) &&           max(A.y,B.y) >= min(C.y,D.y) &&           max(C.y,D.y) >= min(A.y,B.y) &&           dcmp(Cross(C-A,B-A)*Cross(D-A,B-A)) <= 0 &&           dcmp(Cross(A-C,D-C)*Cross(B-C,D-C)) <= 0;}Vector Rotate(Point P,Vector A,double rad){     //以P为基准点把向量A旋转rad    return Vector(P.x+A.x*cos(rad)-A.y*sin(rad),P.y+A.x*sin(rad)+A.y*cos(rad));}struct node {    char id;    int cnt;    Line line[23];    vector<char> inter;}poly[33];int cmp(node ka,node kb) { return ka.id < kb.id; }int main(){    char ss[4],shape[20];    int tot = 0,i,j,e,k;    while(scanf("%s",ss)!=EOF)    {        if(ss[0] == ‘.‘) break;        if(ss[0] != ‘-‘) {            poly[++tot].id = ss[0];            scanf("%s",shape);            if(shape[0] == ‘t‘) {                 //triangle                poly[tot].cnt = 3;                Point P[3];                for(i=0;i<3;i++) scanf(" (%lf,%lf)",&P[i].x,&P[i].y);                for(i=0;i<3;i++) poly[tot].line[i] = Line(P[i],P[(i+1)%3]-P[i]);            }            else if(shape[0] == ‘s‘) {            //square                poly[tot].cnt = 4;                Point A,B,C,D;                scanf(" (%lf,%lf)",&A.x,&A.y);                scanf(" (%lf,%lf)",&C.x,&C.y);                B = Rotate(A,C-A,pi*0.25); B = A + (B-A)/sqrt(2.0);                D = C + (A-B);                poly[tot].line[0] = Line(A,B-A), poly[tot].line[1] = Line(B,C-B);                poly[tot].line[2] = Line(C,D-C), poly[tot].line[3] = Line(D,A-D);            }            else if(shape[0] == ‘r‘) {             //rectangle                poly[tot].cnt = 4;                Point A,B,C,D;                scanf(" (%lf,%lf)",&A.x,&A.y);                scanf(" (%lf,%lf)",&B.x,&B.y);                scanf(" (%lf,%lf)",&C.x,&C.y);                D = A + (C-B);                poly[tot].line[0] = Line(A,B-A), poly[tot].line[1] = Line(B,C-B);                poly[tot].line[2] = Line(C,D-C), poly[tot].line[3] = Line(D,A-D);            }            else if(shape[0] == ‘l‘) {             //line                poly[tot].cnt = 1;                Point A,B;                scanf(" (%lf,%lf)",&A.x,&A.y);                scanf(" (%lf,%lf)",&B.x,&B.y);                poly[tot].line[0] = Line(A,B-A);            }            else if(shape[0] == ‘p‘) {             //polygon                scanf("%d",&poly[tot].cnt);                Point P[22];                for(i=0;i<poly[tot].cnt;i++) {                    scanf(" (%lf,%lf)",&P[i].x,&P[i].y);                    if(i >= 1) poly[tot].line[i-1] = Line(P[i-1],P[i]-P[i-1]);                }                poly[tot].line[i-1] = Line(P[i-1],P[0]-P[i-1]);            }        }        else                                    //processing...        {            for(i=1;i<=tot;i++)                 //处理第i个多边形            {                poly[i].inter.clear();                for(e=0;e<poly[i].cnt;e++)      //枚举每条边                {                    for(j=1;j<=tot;j++)         //枚举别的多边形                    {                        if(i == j) continue;                        for(k=0;k<poly[j].cnt;k++)   //枚举别的多边形的每条边                        {                            Point A = poly[i].line[e].p, B = poly[i].line[e].p+poly[i].line[e].v;                            Point C = poly[j].line[k].p, D = poly[j].line[k].p+poly[j].line[k].v;                            if(SegmentIntersection(A,B,C,D))                            {                                poly[i].inter.push_back(poly[j].id);                                break;                            }                        }                    }                }                sort(poly[i].inter.begin(),poly[i].inter.end());                poly[i].inter.erase(unique(poly[i].inter.begin(),poly[i].inter.end()),poly[i].inter.end());            }            sort(poly+1,poly+tot+1,cmp);            for(i=1;i<=tot;i++) {                printf("%c",poly[i].id);                int sz = poly[i].inter.size();                if(sz == 0)                    puts(" has no intersections");                else {                    printf(" intersects with ");                    if(sz == 1)                        printf("%c\n",poly[i].inter[0]);                    else if(sz == 2)                        printf("%c and %c\n",poly[i].inter[0],poly[i].inter[1]);                    else {                        for(j=0;j<sz-1;j++) printf("%c, ",poly[i].inter[j]);                        printf("and %c\n",poly[i].inter[j]);                    }                }            }            puts("");            tot = 0;        }    }    return 0;}