Geometric Shapes

题目大意：给一些几何图形的编号，求出来这些图形都和那些相交。

 

分析：输入的正方形对角线上的两个点，所以需要求出来另外两个点，公式是：

x2:=(x1+x3+y3-y1)/2; y2:=(y1+y3+x1-x3)/2;

x4:=(x1+x3-y3+y1)/2; y4:=(y1+y3-x1+x3)/2;

这个是可以推倒出来的，有兴趣的可以推一下，给的矩形三个点，是按照顺序给的，求出来第四个点即可，比较容易求，x4=x1-x2+x3， y4=y1-y2+y3

别的图形的点也都是按照顺序给的，两个图形如果相交一定是边的相交，一个图形把另一个包含不算相交。所以处理完输入输出，还是比较容易做的。

 

代码如下：

========================================================================================================================

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<algorithm>
using namespace std;

const int MAXN = 26;
const double EPS = 1e-8;

int Sign(double t)
{
    if(t > EPS)return 1;
    if(fabs(t) < EPS)return 0;
    return -1;
}
struct Point
{
    double x, y;
    Point(double x=0, double y=0):x(x),y(y){}
    Point operator - (const Point &tmp)const{
        return Point(x-tmp.x, y-tmp.y);
    }
    double operator ^(const Point &tmp)const{
        return x*tmp.y - y*tmp.x;
    }
};
struct Segment
{
    Point S, E;
    Segment(Point S=0, Point E=0):S(S), E(E){}
    bool Intersect(const Segment &tmp)const{
        int t1 = Sign((S-E)^(tmp.S-E));
        int t2 = Sign((S-E)^(tmp.E-E));

        return abs(t1+t2) != 2;
    }
};
struct Shapes
{
    Segment sg[MAXN];
    int N;
};
bool Find(int u, int v, Shapes a[])
{
    for(int i=0; i<a[u].N; i++)
    for(int j=0; j<a[v].N; j++)
    {
        if(a[u].sg[i].Intersect(a[v].sg[j]) && a[v].sg[j].Intersect(a[u].sg[i]))
            return true;
    }

    return false;
}
void Link(Shapes a[], int k, Point p[])
{
    int i, N=a[k].N;
    p[N] = p[0];
    for(i=1; i<=N; i++)
        a[k].sg[i-1] = Segment(p[i-1], p[i]);
}
int main()
{
    char Id[MAXN], s[MAXN], s1[MAXN], s2[MAXN];
    Shapes a[MAXN];
    Point p[MAXN];

    memset(a, 0, sizeof(a));

    while(scanf("%s", Id) != EOF && Id[0] != '.')
    {
        if(Id[0] == '-')
        {
            for(int i=0; i<MAXN; i++)
            {
                if(a[i].N)
                {///如果这个符号的形状存在
                    int ans[MAXN], k=0;
                    for(int j=0; j<MAXN; j++)
                    {
                        if(!a[j].N || i==j)
                            continue;
                        if(Find(i, j, a) == true)
                            ans[k++] = j;
                    }

                    if(k == 1)
                        printf("%c intersects with %c
", i+'A', ans[0]+'A');
                    else if(k == 0)
                        printf("%c has no intersections
", i+'A');
                    else
                    {
                        printf("%c intersects with %c", i+'A', ans[0]+'A');
                        for(int t=1; t<k-1; t++)
                            printf(", %c", ans[t]+'A');
                        if(k == 2)
                            printf(" and %c
", ans[k-1]+'A');
                        else
                            printf(", and %c
", ans[k-1]+'A');
                    }
                }
            }
            printf("
");
            memset(a, 0, sizeof(a));
        }
        else
        {
            scanf("%s", s);
            int k = Id[0] - 'A';

            if(strcmp(s, "square") == 0)
            {///正方形
                a[k].N = 4;
                scanf("%s%s", s1, s2);
                sscanf(s1, "(%lf,%lf)", &p[0].x, &p[0].y);
                sscanf(s2, "(%lf,%lf)", &p[2].x, &p[2].y);

                p[1].x = (p[0].x+p[2].x + p[2].y-p[0].y)/2;
                p[1].y = (p[0].x-p[2].x + p[0].y+p[2].y)/2;
                p[3].x = (p[0].x+p[2].x + p[0].y-p[2].y)/2;
                p[3].y = (p[2].x-p[0].x + p[0].y+p[2].y)/2;
            }
            else if(strcmp(s, "line") == 0)
            {///直线
                a[k].N = 2;
                scanf("%s%s", s1, s2);
                sscanf(s1, "(%lf,%lf)", &p[0].x, &p[0].y);
                sscanf(s2, "(%lf,%lf)", &p[1].x, &p[1].y);
            }
            else if(strcmp(s, "rectangle") == 0)
            {///长方形
                a[k].N = 4;
                for(int t=0; t<3; t++)
                {
                    scanf("%s", s1);
                    sscanf(s1, "(%lf,%lf)", &p[t].x, &p[t].y);
                }
                p[3].x = p[0].x-p[1].x+p[2].x;
                p[3].y = p[0].y-p[1].y+p[2].y;
            }
            else if(strcmp(s, "triangle") == 0)
            {///三角形
                a[k].N = 3;
                for(int t=0; t<3; t++)
                {
                    scanf("%s", s1);
                    sscanf(s1, "(%lf,%lf)", &p[t].x, &p[t].y);
                }
            }
            else if(strcmp(s, "polygon") == 0)
            {///多边形
                scanf("%d", &a[k].N);

                for(int t=0; t<a[k].N; t++)
                {
                    scanf("%s", s1);
                    sscanf(s1, "(%lf,%lf)", &p[t].x, &p[t].y);
                }
            }

            Link(a, k, p);
        }
    }

    return 0;
}