首页 > ACM题库 > HDU-杭电 > hdu 2327 Geometric Shapes[解题报告]C++
2014
01-05

hdu 2327 Geometric Shapes[解题报告]C++

Geometric Shapes

问题描述 :

While creating a customer logo, ACM uses graphical utilities to draw a picture that can later be cut into special fluorescent materials. To ensure proper processing, the shapes in the picture cannot intersect. However, some logos contain such intersecting shapes. It is necessary to detect them and decide how to change the picture.

Given a set of geometric shapes, you are to determine all of their intersections. Only outlines are considered, if a shape is completely inside another one, it is not counted as an intersection.

输入:

Input contains several pictures. Each picture describes at most 26 shapes, each specified on a separate line. The line begins with an uppercase letter that uniquely identifies the shape inside the corresponding picture. Then there is a kind of the shape and two or more points, everything separated by at least one space. Possible shape kinds are:

• square: Followed by two distinct points giving the opposite corners of the square.
• rectangle: Three points are given, there will always be a right angle between the lines connecting the first point with the second and the second with the third.
• line: Specifies a line segment, two distinct end points are given.
• triangle: Three points are given, they are guaranteed not to be co-linear.
• polygon: Followed by an integer number N (3 ≤ N ≤ 20) and N points specifying vertices of the polygon in either clockwise or anti-clockwise order. The polygon will never intersect itself and its sides will have non-zero length.

All points are always given as two integer coordinates X and Y separated with a comma and enclosed in parentheses. You may assume that |X|, |Y | ≤ 10000.

The picture description is terminated by a line containing a single dash (“-”). After the last picture, there is a line with one dot (“.”).

输出:

Input contains several pictures. Each picture describes at most 26 shapes, each specified on a separate line. The line begins with an uppercase letter that uniquely identifies the shape inside the corresponding picture. Then there is a kind of the shape and two or more points, everything separated by at least one space. Possible shape kinds are:

• square: Followed by two distinct points giving the opposite corners of the square.
• rectangle: Three points are given, there will always be a right angle between the lines connecting the first point with the second and the second with the third.
• line: Specifies a line segment, two distinct end points are given.
• triangle: Three points are given, they are guaranteed not to be co-linear.
• polygon: Followed by an integer number N (3 ≤ N ≤ 20) and N points specifying vertices of the polygon in either clockwise or anti-clockwise order. The polygon will never intersect itself and its sides will have non-zero length.

All points are always given as two integer coordinates X and Y separated with a comma and enclosed in parentheses. You may assume that |X|, |Y | ≤ 10000.

The picture description is terminated by a line containing a single dash (“-”). After the last picture, there is a line with one dot (“.”).

样例输入:

A square (1,2) (3,2)
F line (1,3) (4,4)
W triangle (3,5) (5,5) (4,3)
X triangle (7,2) (7,4) (5,3)
S polygon 6 (9,3) (10,3) (10,4) (8,4) (8,1) (10,2)
B rectangle (3,3) (7,5) (8,3)
-
B square (1,1) (2,2)
A square (3,3) (4,4)
-
.

样例输出:

A has no intersections
B intersects with S, W, and X
F intersects with W
S intersects with B
W intersects with B and F
X intersects with B

A has no intersections
B has no intersections

判断多边形是否相交只需把多边形拆成一条条的线段,然后看线段是否相交即可

其中需要注意的是正方形顶点的求法,最好不使用三角函数去求。看我代码中的方法。

然后就比较好搞了

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <map>
#include <sstream>
#include <queue>
#include <vector>
#define MAXN 100005
#define MAXM 211111
#define eps 1e-8
#define INF 50000001
using namespace std;
inline int dblcmp(double d)
{
    if(fabs(d) < eps) return 0;
    return d > eps ? 1 : -1;
}
struct point
{
    double x, y;
    point(){}
    point(double _x, double _y): x(_x), y(_y) {}
    void input()
    {
        scanf("%lf%lf", &x, &y);
    }
    bool operator ==(point a)const
    {
        return dblcmp(a.x - x) == 0 && dblcmp(a.y - y) == 0;
    }
    point sub(point p)
    {
        return point(x - p.x, y - p.y);
    }
    double dot(point p)
    {
        return x * p.x + y * p.y;
    }
    double det(point p)
    {
        return x * p.y - y * p.x;
    }
    double distance(point p)
    {
        return hypot(x - p.x, y - p.y);
    }
}p[33];
struct line
{
    point a, b;
    line(){}
    line(point _a, point _b){ a = _a; b = _b;}
    void input()
    {
        a.input();
        b.input();
    }
    int segcrossseg(line v)
    {
        int d1 = dblcmp(b.sub(a).det(v.a.sub(a)));
        int d2 = dblcmp(b.sub(a).det(v.b.sub(a)));
        int d3 = dblcmp(v.b.sub(v.a).det(a.sub(v.a)));
        int d4 = dblcmp(v.b.sub(v.a).det(b.sub(v.a)));
        if ((d1 ^ d2) == -2 && (d3 ^ d4) == -2)return 2;
        return (d1 == 0 && dblcmp(v.a.sub(a).dot(v.a.sub(b))) <= 0||
                d2 == 0 && dblcmp(v.b.sub(a).dot(v.b.sub(b))) <= 0||
                d3 == 0 && dblcmp(a.sub(v.a).dot(a.sub(v.b))) <= 0||
                d4 == 0 && dblcmp(b.sub(v.a).dot(b.sub(v.b))) <= 0);
    }
    int linecrossseg(line v)//v is seg
    {
        int d1 = dblcmp(b.sub(a).det(v.a.sub(a)));
        int d2 = dblcmp(b.sub(a).det(v.b.sub(a)));
        if ((d1 ^ d2) == -2) return 2;
        return (d1 == 0 || d2 == 0);
    }

    point crosspoint(line v)
    {
        double a1 = v.b.sub(v.a).det(a.sub(v.a));
        double a2 = v.b.sub(v.a).det(b.sub(v.a));
        return point((a.x * a2 - b.x * a1) / (a2 - a1), (a.y * a2 - b.y * a1) / (a2 - a1));
    }

};
struct node
{
    string name;
    vector<line>seg;
};
char sa[55], sb[55];
vector<node>g;
vector<string>ans[55];
bool cmp(node x, node y)
{
    return x.name < y.name;
}
bool ok(int k1, int k2)
{
    int sz1 = g[k1].seg.size();
    int sz2 = g[k2].seg.size();
    for(int i = 0; i < sz1; i++)
        for(int j = 0; j < sz2; j++)
            if(g[k1].seg[i].segcrossseg(g[k2].seg[j])) return true;
    return false;
}
void solve()
{
    for(int i = 0; i < 50; i++) ans[i].clear();
    sort(g.begin(), g.end(), cmp);
    int sz = g.size();
    for(int i = 0; i < sz; i++)
    {
        for(int j = 0; j < sz; j++)
        {
            if(i == j) continue;
            if(ok(i, j)) ans[i].push_back(g[j].name);
        }
    }
    for(int i = 0; i < sz; i++)
    {
        if(ans[i].size() == 0) printf("%s has no intersections\n", g[i].name.c_str());
        else
        {
            if(ans[i].size() == 1)
            {
                printf("%s intersects with %s\n", g[i].name.c_str(), ans[i][0].c_str());
            }
            else if(ans[i].size() == 2)
            {
                printf("%s intersects with %s and %s\n", g[i].name.c_str(), ans[i][0].c_str(), ans[i][1].c_str());
            }
            else
            {
                printf("%s intersects with ", g[i].name.c_str());
                for(int j = 0; j < ans[i].size() - 1; j++) printf("%s, ", ans[i][j].c_str());
                printf("and %s\n", ans[i][ans[i].size() - 1].c_str());
            }
        }
    }
    g.clear();
    printf("\n");
}
int main()
{
    double xa, ya, xb, yb;
    while(scanf("%s", sa) != EOF)
    {
        if(strcmp(sa, "-") == 0)
        {
            solve();
            continue;
        }
        if(strcmp(sa, ".") == 0) break;
        node tmp;
        tmp.name = sa;
        scanf("%s", sb);
        if(sb[0] == 's')
        {
            point a, c;
            scanf(" (%lf,%lf)", &a.x, &a.y);
            scanf(" (%lf,%lf)", &c.x, &c.y);
            point b, d;
            double x, y, mx, my;
            mx = (a.x + c.x)/2.0, my = (a.y + c.y) / 2.0;
            x = a.x - mx;    y = a.y - my;
            b.x = -y + mx;   b.y = x + my;
            x = c.x - mx;    y = c.y - my;
            d.x = - y + mx; d.y = x + my;
            tmp.seg.push_back(line(a, b));
            tmp.seg.push_back(line(b, c));
            tmp.seg.push_back(line(a, d));
            tmp.seg.push_back(line(c, d));
        }
        else if(sb[0] == 'l')
        {
            point a, b;
            scanf(" (%lf,%lf)", &a.x, &a.y);
            scanf(" (%lf,%lf)", &b.x, &b.y);
            tmp.seg.push_back(line(a, b));

        }
        else if(sb[0] == 't')
        {
            point a, b, c;
            scanf(" (%lf,%lf)", &a.x, &a.y);
            scanf(" (%lf,%lf)", &b.x, &b.y);
            scanf(" (%lf,%lf)", &c.x, &c.y);
            tmp.seg.push_back(line(a, b));
            tmp.seg.push_back(line(a, c));
            tmp.seg.push_back(line(b, c));
        }
        else if(sb[0] == 'r')
        {
            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);
            double dx = b.x - a.x;
            d.x = c.x - dx;
            double dy = b.y - a.y;
            d.y = c.y - dy;
            tmp.seg.push_back(line(a, b));
            tmp.seg.push_back(line(b, c));
            tmp.seg.push_back(line(a, d));
            tmp.seg.push_back(line(c, d));
        }
        else
        {
            int t;
            scanf("%d", &t);
            for(int i = 0; i < t; i++) scanf(" (%lf,%lf)", &p[i].x, &p[i].y);
            for(int i = 0; i < t; i++) tmp.seg.push_back(line(p[i], p[(i + 1) % t]));
        }
        g.push_back(tmp);
    }
    return 0;
}

解题转自:http://blog.csdn.net/sdj222555/article/details/13006891


  1. 老实说,这种方法就是穷举,复杂度是2^n,之所以能够AC是应为题目的测试数据有问题,要么数据量很小,要么能够得到k == t,否则即使n = 30,也要很久才能得出结果,本人亲测