poj

#include <cmath>
#include <queue>
#include <algorithm>

using namespace std;

typedef double db;

const db eps = 1e-10;
const db pi = acos(-1.0);

int (db x) {
    return x<-eps?-1:x>eps;
}

db myacos(db x){
    if(x<-1) x = -1;
    if(x>1) x = 1;
    return acos(x);
}

db myasin(db x){
    if(x<-1) x = -1;
    if(x>1) x = 1;
    return asin(x);
}

db mysqrt(db x){
    return x<0?0:sqrt(x);
}

typedef struct P {
    db x, y;
    P(db x = 0, db y = 0) : x(x), y(y) {}
    P operator+(P r){return P(x+r.x,y+r.y);}
    P operator-(P r){return P(x-r.x,y-r.y);}
    P operator*(db r){return P(x*r,y*r);}
    P operator/(db r){return P(x/r,y/r);}
    bool operator<(const P &r)const{return x<r.x||(x==r.x&&y<r.y);}
    bool operator==(const P &r)const{return dcmp(x-r.x)==0&&dcmp(y-r.y)==0;}
    
    void read(){ scanf(" (%lf,%lf)", &x, &y); }
}V;

//向量a的极角
db Angle(const V& v) {
    return atan2(v.y, v.x);
}

//向量点积
db Dot(V A, V B) { return A.x*B.x + A.y*B.y; }

//向量长度
db Length(V A) { return mysqrt(Dot(A, A)); }

//向量夹角
db Angle(V A, V B) { return myacos(Dot(A, B) / Length(A) / Length(B)); }

//向量叉积
db Cross(V A, V B) { return A.x*B.y - A.y*B.x; }

char s[20];
int n;

P GetLineIntersection(P p, V v, P q, V w) {
    V u = p - q;
    db t = Cross(w, u)/Cross(v, w);
    return p+v*t;
}

//判断点是否在点段上，不包含端点
bool OnSegment(P p, P a1, P a2) {
    return dcmp(Cross(a1-p, a2-p) == 0 && dcmp((Dot(a1-p, a2-p)) < 0));
}

//向量逆时针旋转rad度(弧度)
V Rotate(V A, db rad) {
    return V(A.x*cos(rad)-A.y*sin(rad), A.x*sin(rad)+A.y*cos(rad));
}

struct node{
    P a[25];
    int n;
    char ch;
}r[200];

bool SegmentProperIntersection(P a1, P a2, P b1, P b2) {
    db c1 = Cross(a2-a1, b1-a1), c2 = Cross(a2-a1, b2-a1);
    db c3 = Cross(b2-b1, a1-b1), c4 = Cross(b2-b1, a2-b1);
    return dcmp(c1)*dcmp(c2) < 0 && dcmp(c3)*dcmp(c4) < 0;
}

//不规范相交
bool on(P a1, P a2, P b1, P b2){
    if(OnSegment(a1, b1, b2))return true;
    if(OnSegment(a2, b1, b2))return true;
    if(OnSegment(b1, a1, a2))return true;
    if(OnSegment(b2, a1, a2))return true;
    if(a1 == b1 || a1 == b2 || a2 == b1 || a2 == b2)return true;
    return SegmentProperIntersection(a1, a2, b1, b2);
}

bool check(int x, int y){
    for(int i = 1; i <= r[x].n; i++){
        for(int j = 1; j <= r[y].n; j++){
                if(on(r[x].a[i], r[x].a[i - 1], r[y].a[j], r[y].a[j - 1])){
                   // if(x == 0 && y == 2)printf("%.2f %.2f %.2f %.2f %.2f %.2f %.2f %.2fn", r[x].a[i].x, r[x].a[i].y,r[x].a[i - 1].x, r[x].a[i - 1].y, r[y].a[j].x, r[y].a[j].y, r[y].a[j - 1].x, r[y].a[j - 1].y);
                    return true;
                }
            }
        }
    return false;
}


bool cmp(node &x, node &y){
    return x.ch < y.ch;
}

bool cmp1(int x, int y){
    return r[x].ch < r[y].ch;
}

int main(){
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    while(1){
        n = 0;
        while(scanf("%s", s) && s[0] != '-' && s[0] != '.'){
            r[n].ch = s[0];
            scanf("%s", s);
            if(s[0] == 's'){
                r[n].a[0].read();
                r[n].a[2].read();
                V v1 = r[n].a[2] - r[n].a[0];
                V v2 = Rotate(v1, pi / 2);
                V v3 = Rotate(v1, -pi / 2);
                P mid = (r[n].a[0] + r[n].a[2]) / 2;
                r[n].a[1] = mid + (v2) / 2;
                r[n].a[3] = mid + (v3) / 2;
                r[n].n = 4;
                n++;
            }
            else if(s[0] == 't'){
                r[n].n = 3;
                for(int i = 0; i < 3; i++)r[n].a[i].read();
                n++;
            }
            else if(s[0] == 'l'){
                r[n].n = 2;
                for(int i = 0; i < 2; i++){
                    r[n].a[i].read();
                }
                n++;
            }
            else if(s[0] == 'p'){
                scanf("%d", &r[n].n);
                for(int i = 0; i < r[n].n; i++)r[n].a[i].read();
                n++;
            }
            else{
                r[n].n = 4;
                for(int i = 0; i < 3; i++)r[n].a[i].read();
                r[n].a[3] = r[n].a[2] + r[n].a[0] - r[n].a[1];
                n++;
            }
        }

        for(int i = 0; i < n; i++)r[i].a[r[i].n] = r[i].a[0];
        sort(r, r + n, cmp);

        for(int i = 0; i < n; i++){
            vector<int> res;
            for(int j = 0; j < n; j++){
                if(i == j)continue;
                if(check(i, j))res.push_back(j);
            }
            if(!res.size()){
                printf("%c has no intersectionsn", r[i].ch);
                continue;
            }
            sort(res.begin(), res.end(), cmp1);
            printf("%c intersects with", r[i].ch);
            if(res.size() == 1)printf(" %cn", r[res[0]].ch);
            else if(res.size() == 2) printf(" %c and %cn", r[res[0]].ch, r[res[1]].ch);
            else{
                for(int j = 0; j < res.size() - 1; j++){
                    printf(" %c,", r[res[j]].ch);
                }
                printf(" and %cn", r[res[res.size() - 1]].ch);
            }
        }
        puts("");
        if(s[0] == '.')break;
    }
    return 0;
}