2014
01-05

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:

&#8226; square: Followed by two distinct points giving the opposite corners of the square.
&#8226; 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.
&#8226; line: Specifies a line segment, two distinct end points are given.
&#8226; triangle: Three points are given, they are guaranteed not to be co-linear.
&#8226; 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:

&#8226; square: Followed by two distinct points giving the opposite corners of the square.
&#8226; 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.
&#8226; line: Specifies a line segment, two distinct end points are given.
&#8226; triangle: Three points are given, they are guaranteed not to be co-linear.
&#8226; 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;
}

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