POJ 3449 Geometric Shapes

Description:

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.

img

Input:

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 (“.”).

Output:

For each picture, output one line for each of the shapes, sorted alphabetically by its identifier (X). The line must be one of the following:

• “X has no intersections”, if X does not intersect with any other shapes.
• “X intersects with A”, if X intersects with exactly 1 other shape.
• “X intersects with A and B”, if X intersects with exactly 2 other shapes.
• “X intersects with A, B, . . ., and Z”, if X intersects with more than 2 other shapes.

Please note that there is an additional comma for more than two intersections. A, B, etc. are all intersecting shapes, sorted alphabetically.

Print one empty line after each picture, including the last one.

Sample Input:

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)
-
.

Sample Output:

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

题目链接

给出一些图形(直线、三角形、正方形、长方形、多边形),求每个图形与哪些图形相交。

矩形(正方形、长方形)只给出一对顶点,需要求出另外两顶点。

对每个图形存其所有的边,枚举图形,遍历其它图形,暴力判断是否有边相交即可。

AC代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;

const int maxn = 1e2 + 5;
const double eps = 1e-8;

int Sgn(double X) {
if (fabs(X) < eps) {
return 0;
}
if (X < 0) {
return -1;
}
else {
return 1;
}
}

struct Point {
double X, Y;

Point() {}
Point(double _X, double _Y) {
X = _X;
Y = _Y;
}

void Input() {
scanf("%lf%lf", &X, &Y);
}

Point operator - (const Point &B) const {
return Point(X - B.X, Y - B.Y);
}

double operator * (const Point &B) const {
return X * B.X + Y * B.Y;
}

double operator ^ (const Point &B) const {
return X * B.Y - Y * B.X;
}
};

struct Segment {
char Code;
Point S, T;

Segment() {}
Segment(char _Code, Point _S, Point _T) {
Code = _Code;
S = _S;
T = _T;
}

void Input() {
S.Input();
T.Input();
}

double operator ^ (const Segment &B) const {
return (T - S) ^ (B.T - B.S);
}
};

bool IsIntersect(Segment A, Segment B) {
return
max(A.S.X, A.T.X) >= min(B.S.X, B.T.X) &&
max(B.S.X, B.T.X) >= min(A.S.X, A.T.X) &&
max(A.S.Y, A.T.Y) >= min(B.S.Y, B.T.Y) &&
max(B.S.Y, B.T.Y) >= min(A.S.Y, A.T.Y) &&
Sgn((B.S - A.T) ^ (A.S - A.T)) * Sgn((B.T - A.T) ^ (A.S - A.T)) <= 0 &&
Sgn((A.S - B.T) ^ (B.S - B.T)) * Sgn((A.T - B.T) ^ (B.S - B.T)) <= 0;
}

int Cnt;
Point points[maxn];
char Str[maxn];
char Code;
char Shape[maxn];
vector<Segment> Graph[maxn];
vector<char> Ans[maxn];

bool Cmp(vector<Segment> A, vector<Segment> B) {
return A[0].Code < B[0].Code;
}

bool Input() {
for (int i = 0; i < Cnt; ++i) {
Graph[i].clear();
Ans[i].clear();
}
Cnt = 0;
while (true) {
scanf("%c", &Code);
if (Code == '-') {
getchar();
return true;
}
else if (Code == '.') {
return false;
}
scanf("%s", Shape);
if (!strcmp(Shape, "line")) {
scanf(" (%lf,%lf) (%lf,%lf)", &points[0].X, &points[0].Y, &points[1].X, &points[1].Y);
Graph[Cnt].push_back(Segment(Code, points[0], points[1]));
}
else if (!strcmp(Shape, "triangle")) {
scanf(" (%lf,%lf) (%lf,%lf) (%lf,%lf)", &points[0].X, &points[0].Y, &points[1].X, &points[1].Y, &points[2].X, &points[2].Y);
Graph[Cnt].push_back(Segment(Code, points[0], points[1]));
Graph[Cnt].push_back(Segment(Code, points[2], points[1]));
Graph[Cnt].push_back(Segment(Code, points[0], points[2]));
}
else if (!strcmp(Shape, "square")) {
scanf(" (%lf,%lf) (%lf,%lf)", &points[0].X, &points[0].Y, &points[1].X, &points[1].Y);
points[2].X = (points[0].X + points[0].Y + points[1].X - points[1].Y) / 2;
points[2].Y = (-points[0].X + points[0].Y + points[1].X + points[1].Y) / 2;
points[3].X = (points[0].X - points[0].Y + points[1].X + points[1].Y) / 2;
points[3].Y = (points[0].X + points[0].Y - points[1].X + points[1].Y) / 2;
Graph[Cnt].push_back(Segment(Code, points[0], points[2]));
Graph[Cnt].push_back(Segment(Code, points[2], points[1]));
Graph[Cnt].push_back(Segment(Code, points[1], points[3]));
Graph[Cnt].push_back(Segment(Code, points[3], points[0]));
}
else if (!strcmp(Shape, "rectangle")) {
scanf(" (%lf,%lf) (%lf,%lf) (%lf,%lf)", &points[0].X, &points[0].Y, &points[1].X, &points[1].Y, &points[2].X, &points[2].Y);
points[3].X = points[0].X + points[2].X - points[1].X;
points[3].Y = points[0].Y + points[2].Y - points[1].Y;
Graph[Cnt].push_back(Segment(Code, points[0], points[1]));
Graph[Cnt].push_back(Segment(Code, points[1], points[2]));
Graph[Cnt].push_back(Segment(Code, points[2], points[3]));
Graph[Cnt].push_back(Segment(Code, points[3], points[0]));
}
else if (!strcmp(Shape, "polygon")) {
int Num;
scanf("%d", &Num);
for (int i = 0; i < Num; ++i) {
scanf(" (%lf,%lf)", &points[i].X, &points[i].Y);
if (i) {
Graph[Cnt].push_back(Segment(Code, points[i - 1], points[i]));
}
}
Graph[Cnt].push_back(Segment(Code, points[0], points[Num - 1]));
}
Cnt++;
getchar();
}
}

void Check(int X, int Y) {
for (int i = 0; i < int(Graph[X].size()); ++i) {
for (int j = 0; j < int(Graph[Y].size()); ++j) {
if (IsIntersect(Graph[X][i], Graph[Y][j])) {
Ans[X].push_back(Graph[Y][j].Code);
Ans[Y].push_back(Graph[X][i].Code);
return;
}
}
}
}

void Output(int X) {
if (int(Ans[X].size()) == 0) {
printf("%c has no intersections\n", Graph[X][0].Code);
}
else if (int(Ans[X].size()) == 1) {
printf("%c intersects with %c\n", Graph[X][0].Code, Ans[X][0]);
}
else if (int(Ans[X].size()) == 2) {
printf("%c intersects with %c and %c\n", Graph[X][0].Code, Ans[X][0], Ans[X][1]);
}
else {
printf("%c intersects with ", Graph[X][0].Code);
for (int i = 0; i < int(Ans[X].size()) - 1; ++i) {
printf("%c, ", Ans[X][i]);
}
printf("and %c\n", Ans[X].back());
}
}

void Solve() {
sort(Graph, Graph + Cnt, Cmp);
for (int i = 0; i < Cnt; ++i) {
for (int j = i + 1; j < Cnt; ++j) {
Check(i, j);
}
Output(i);
}
}

// POJ-3449交C++

int main(int argc, char *argv[]) {
while (Input()) {
Solve();
printf("\n");
}
return 0;
}
文章目录
  1. 1. Description:
  2. 2. Input:
  3. 3. Output:
  4. 4. Sample Input:
  5. 5. Sample Output:
    1. 5.1. 题目链接
  6. 6. AC代码:
|