题意： 给一些多边形或线段，输出与每一个多边形或线段的有哪一些多边形或线段。
解法： 想法不难，直接暴力将所有的图形处理成线段，然后暴力枚举，相交就加入其vector就行了。主要是代码有点麻烦，一步一步来吧。
还有收集了一个线段旋转的函数。
给定正方形对角求其他两点用到了线段旋转。
Vector Rotate(Point P,Vector A,double rad){ //以P为基准点把向量A旋转rad
return Vector(P.x+A.x*cos(rad)-A.y*sin(rad),P.y+A.x*sin(rad)+A.y*cos(rad));
}
从POJ Discuss上面搞了一点数据下来：
【input】 Z line (,) (,)
A square (,) (,)
R polygon (,) (-,-) (,-) (,) (-,-)
V line (,) (-,)
P line (-,-) (-,)
S rectangle (,-) (,-) (,-)
B triangle (-,) (,) (,)
T line (-,) (-,)
L triangle (-,) (-,) (,)
M rectangle (-,) (,-) (,-)
N line (-,) (-,)
O square (,-) (,)
C line (-,) (,)
Q square (-,-) (-,)
-
D line (-,-) (-,)
K line (,) (-,)
H square (-,-) (-,)
C rectangle (-,-) (,) (-,-)
M line (,) (-,)
W rectangle (,) (-,-) (,)
T square (,-) (,)
Z rectangle (,-) (,-) (,-)
E line (,) (-,-)
A rectangle (-,-) (-,) (-,)
F rectangle (,-) (,-) (,-)
G line (,) (,)
I triangle (,-) (,) (-,)
Q line (-,) (,)
N line (,-) (-,)
-
Q polygon (,) (-,) (,) (,) (,-) (-,-) (-,)
A rectangle (-,-) (-,-) (-,)
K triangle (-,) (,-) (-,-)
J square (,) (,-)
X square (-,-) (,)
S line (,-) (,)
E rectangle (-,-) (-,-) (-,)
O triangle (-,-) (,-) (,)
F rectangle (,-) (,-) (,-)
-
W square (,-) (,)
X polygon (,) (-,-) (,)
T square (-,-) (-,)
K square (,-) (,)
E rectangle (,) (,) (,)
Y square (-,-) (-,)
V polygon (-,) (,) (,) (,) (,) (,-) (-,-) (-,) (-,-) (,)
Z polygon (-,) (-,) (-,) (,-) (,) (,) (,-) (,)
B polygon (,-) (,) (,) (,) (,) (,) (-,) (-,-) (,-) (-,) (-,)
A rectangle (-,-) (,) (-,-)
U rectangle (,-) (-,-) (,)
H triangle (-,) (,-) (,)
C square (-,) (,)
D rectangle (,) (,-) (,)
F square (-,) (,-)
G rectangle (-,) (,-) (,-)
Q triangle (-,) (-,) (,-)
S square (-,-) (,)
R line (,-) (,-)
I square (,) (,-)
J line (,) (,)
L triangle (-,-) (,) (,-)
M rectangle (-,-) (,-) (,-)
-
Q polygon (-,) (,) (-,) (-,) (-,-) (,-) (,-) (,) (,) (,) (,) (-,)
X line (-,) (,)
K square (,-) (,-)
Y polygon (,-) (,) (-,-) (,)
Z polygon (,-) (,-) (,-) (,-) (,-) (-,-) (-,-) (,) (-,-) (,-) (,) (,-) (,)
C polygon (,) (-,) (,) (-,-) (,-) (,-) (,) (,) (,)
F polygon (,) (,) (-,) (,) (,) (-,) (,)
A square (,-) (,)
U polygon (,) (,) (,) (-,) (,) (,) (-,) (-,) (,) (-,) (-,-)
G rectangle (,) (-,) (,)
D polygon (,-) (-,) (,) (,) (,) (,-) (,) (,-) (,)
-
P polygon (-,) (,) (,) (,) (,-) (-,-) (-,-) (-,-) (,-) (-,-) (,)
O triangle (,) (,) (,)
G rectangle (,) (-,-) (,)
M square (-,-) (-,)
K line (-,) (-,-)
E triangle (,) (,-) (,)
X square (,-) (,)
-
E square (-,-) (-,)
X polygon (,-) (-,-) (-,-) (,-) (-,)
O rectangle (-,) (-,) (,-)
M square (,-) (-,-)
I polygon (,) (,-) (,-) (,) (,) (-,) (,) (-,) (-,) (-,) (,) (-,-)
C square (-,-) (-,)
D line (,-) (-,)
N polygon (,) (,) (,) (,) (-,) (,-) (-,-) (-,-) (-,-) (-,) (,) (,)
P line (,-) (-,-)
Y triangle (,-) (,) (-,-)
-
U polygon (,) (,) (,) (,-) (,-) (-,) (-,-) (-,) (-,) (,) (-,)
O square (-,) (,-)
B triangle (,-) (-,-) (,)
H line (,-) (-,)
E rectangle (-,-) (,-) (,-)
Q rectangle (-,-) (-,-) (,-)
P rectangle (-,-) (-,-) (-,)
-
O square (,-) (-,)
I square (-,) (,-)
X polygon (,-) (-,) (-,-) (-,-)
U square (-,) (,)
Z triangle (-,-) (,) (-,)
Y rectangle (,-) (,-) (,-)
-
G triangle (,-) (,) (,-)
C square (,) (-,)
O rectangle (,-) (,-) (,-)
J rectangle (-,-) (-,) (-,)
K polygon (-,) (,-) (,-) (,-) (,) (,) (,) (,-) (,-) (,-) (-,-)
H square (-,-) (,)
Z triangle (,) (-,) (,-)
D rectangle (,-) (-,) (-,)
R rectangle (-,) (,) (-,-)
W triangle (,) (,) (,-)
A triangle (,-) (,-) (,)
U square (-,-) (-,-)
L square (,) (,-)
T square (,) (,-)
X rectangle (,-) (,) (-,-)
M triangle (,) (,) (,)
B line (,) (,)
F rectangle (,) (,-) (,-)
I polygon (-,-) (-,-) (-,-) (,-) (,) (,)
N triangle (,) (,) (,)
Y square (,) (-,-)
P polygon (,) (-,) (-,-) (,-) (-,-) (,) (-,) (,)
Q square (,) (,-)
E square (,-) (,)
S square (,) (-,-)
V triangle (-,) (,) (,)
-
. 【output】
A intersects with Z
B intersects with L, N, O, P, Q, R, T, and V
C intersects with N, O, P, Q, and R
L intersects with B, P, Q, R, T, and Z
M intersects with O, R, and S
N intersects with B and C
O intersects with B, C, M, P, Q, R, S, and V
P intersects with B, C, L, O, Q, R, and V
Q intersects with B, C, L, O, P, R, and V
R intersects with B, C, L, M, O, P, Q, and V
S intersects with M and O
T intersects with B and L
V intersects with B, O, P, Q, R, and Z
Z intersects with A, L, and V A intersects with C, D, E, T, and W
C intersects with A, H, I, and T
D intersects with A and E
E intersects with A, D, G, H, I, K, M, N, Q, and T
F intersects with H, I, T, and Z
G intersects with E, K, and Q
H intersects with C, E, F, I, K, N, Q, T, W, and Z
I intersects with C, E, F, H, K, N, T, W, and Z
K intersects with E, G, H, I, N, T, and W
M intersects with E, N, and Q
N intersects with E, H, I, K, M, Q, T, and W
Q intersects with E, G, H, M, and N
T intersects with A, C, E, F, H, I, K, N, W, and Z
W intersects with A, H, I, K, N, and T
Z intersects with F, H, I, and T A intersects with K, O, and X
E intersects with O and X
F has no intersections
J intersects with K, O, Q, and X
K intersects with A, J, O, Q, and X
O intersects with A, E, J, K, Q, and X
Q intersects with J, K, O, S, and X
S intersects with Q
X intersects with A, E, J, K, O, and Q A intersects with B, F, G, L, M, Q, S, V, W, Y, and Z
B intersects with A, C, D, F, G, H, I, J, K, L, M, Q, S, T, U, V, W, X, Y, and Z
C intersects with B, D, E, F, H, I, J, L, S, T, U, V, W, X, and Z
D intersects with B, C, E, F, G, H, I, J, L, S, U, W, X, and Z
E intersects with C, D, F, I, L, U, and X
F intersects with A, B, C, D, E, G, H, L, M, Q, U, V, W, X, Y, and Z
G intersects with A, B, D, F, H, L, M, U, V, X, and Z
H intersects with B, C, D, F, G, I, J, L, M, S, T, U, V, W, X, and Z
I intersects with B, C, D, E, H, J, K, L, S, U, V, W, X, and Z
J intersects with B, C, D, H, I, U, V, W, X, and Z
K intersects with B, I, V, W, and Z
L intersects with A, B, C, D, E, F, G, H, I, M, Q, U, V, W, X, Y, and Z
M intersects with A, B, F, G, H, L, Q, S, U, V, W, and X
Q intersects with A, B, F, L, M, S, T, U, V, W, X, and Y
R intersects with V
S intersects with A, B, C, D, H, I, M, Q, T, U, V, W, X, Y, and Z
T intersects with B, C, H, Q, S, V, W, Y, and Z
U intersects with B, C, D, E, F, G, H, I, J, L, M, Q, S, V, W, X, and Z
V intersects with A, B, C, F, G, H, I, J, K, L, M, Q, R, S, T, U, W, X, Y, and Z
W intersects with A, B, C, D, F, H, I, J, K, L, M, Q, S, T, U, V, X, Y, and Z
X intersects with B, C, D, E, F, G, H, I, J, L, M, Q, S, U, V, W, and Z
Y intersects with A, B, F, L, Q, S, T, V, W, and Z
Z intersects with A, B, C, D, F, G, H, I, J, K, L, S, T, U, V, W, X, and Y A intersects with C, D, F, G, K, Q, U, Y, and Z
C intersects with A, D, F, G, K, Q, U, X, Y, and Z
D intersects with A, C, F, G, K, Q, U, X, Y, and Z
F intersects with A, C, D, G, Q, U, X, Y, and Z
G intersects with A, C, D, F, Q, U, X, Y, and Z
K intersects with A, C, D, Q, Y, and Z
Q intersects with A, C, D, F, G, K, U, X, Y, and Z
U intersects with A, C, D, F, G, Q, X, Y, and Z
X intersects with C, D, F, G, Q, U, Y, and Z
Y intersects with A, C, D, F, G, K, Q, U, X, and Z
Z intersects with A, C, D, F, G, K, Q, U, X, and Y E intersects with O, P, and X
G intersects with M, P, and X
K intersects with M and P
M intersects with G, K, P, and X
O intersects with E, P, and X
P intersects with E, G, K, M, O, and X
X intersects with E, G, M, O, and P C intersects with E, I, M, N, X, and Y
D intersects with I, N, X, and Y
E intersects with C, I, M, N, O, X, and Y
I intersects with C, D, E, M, N, O, X, and Y
M intersects with C, E, I, N, O, X, and Y
N intersects with C, D, E, I, M, P, X, and Y
O intersects with E, I, M, X, and Y
P intersects with N
X intersects with C, D, E, I, M, N, O, and Y
Y intersects with C, D, E, I, M, N, O, and X B intersects with E, H, O, P, Q, and U
E intersects with B, H, O, P, Q, and U
H intersects with B, E, O, P, Q, and U
O intersects with B, E, H, P, Q, and U
P intersects with B, E, H, O, Q, and U
Q intersects with B, E, H, O, P, and U
U intersects with B, E, H, O, P, and Q I intersects with O, X, and Z
O intersects with I, X, and Z
U has no intersections
X intersects with I, O, and Z
Y has no intersections
Z intersects with I, O, and X A intersects with C, E, H, I, K, L, N, P, Q, S, T, and W
B intersects with H, K, N, P, T, V, W, and Z
C intersects with A, E, F, G, H, I, J, K, L, M, N, P, Q, R, S, V, W, X, Y, and Z
D intersects with I, J, K, L, P, R, T, X, and Z
E intersects with A, C, F, H, I, K, L, N, P, Q, S, T, W, and Z
F intersects with C, E, G, H, I, K, L, O, P, Q, S, T, X, Y, and Z
G intersects with C, F, H, I, K, L, N, P, Q, S, T, V, Y, and Z
H intersects with A, B, C, E, F, G, I, K, L, N, P, Q, R, S, T, U, W, Y, and Z
I intersects with A, C, D, E, F, G, H, J, K, L, M, N, P, Q, R, S, T, V, W, Y, and Z
J intersects with C, D, I, K, L, P, R, T, and X
K intersects with A, B, C, D, E, F, G, H, I, J, L, M, N, O, P, Q, R, S, T, W, X, Y, and Z
L intersects with A, C, D, E, F, G, H, I, J, K, M, P, Q, R, S, T, V, W, X, Y, and Z
M intersects with C, I, K, L, N, S, T, V, and W
N intersects with A, B, C, E, G, H, I, K, M, P, Q, S, T, V, W, Y, and Z
O intersects with F, K, P, R, and T
P intersects with A, B, C, D, E, F, G, H, I, J, K, L, N, O, Q, R, S, T, U, V, W, X, Y, and Z
Q intersects with A, C, E, F, G, H, I, K, L, N, P, S, T, W, Y, and Z
R intersects with C, D, H, I, J, K, L, O, P, S, T, X, and Y
S intersects with A, C, E, F, G, H, I, K, L, M, N, P, Q, R, V, W, and Y
T intersects with A, B, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, V, W, X, Y, and Z
U intersects with H and P
V intersects with B, C, G, I, L, M, N, P, S, T, W, Y, and Z
W intersects with A, B, C, E, H, I, K, L, M, N, P, Q, S, T, and V
X intersects with C, D, F, J, K, L, P, R, T, and Z
Y intersects with C, F, G, H, I, K, L, N, P, Q, R, S, T, V, and Z
Z intersects with B, C, D, E, F, G, H, I, K, L, N, P, Q, T, V, X, and Y
---------------------------------------------------------------------
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
#define pi acos(-1.0)
#define eps 1e-8
using namespace std; struct Point{
double x,y;
Point(double x=, double y=):x(x),y(y) {}
void input() { scanf("%lf%lf",&x,&y); }
};
typedef Point Vector;
struct Line{
Point p;
Vector v;
double ang;
Line(){}
Line(Point p, Vector v):p(p),v(v) { ang = atan2(v.y,v.x); }
Point point(double t) { return Point(p.x + t*v.x, p.y + t*v.y); }
bool operator < (const Line &L)const { return ang < L.ang; }
};
int dcmp(double x) {
if(x < -eps) return -;
if(x > eps) return ;
return ;
}
template <class T> T sqr(T x) { return x * x;}
Vector operator + (Vector A, Vector B) { return Vector(A.x + B.x, A.y + B.y); }
Vector operator - (Vector A, Vector B) { return Vector(A.x - B.x, A.y - B.y); }
Vector operator * (Vector A, double p) { return Vector(A.x*p, A.y*p); }
Vector operator / (Vector A, double p) { return Vector(A.x/p, A.y/p); }
bool operator < (const Point& a, const Point& b) { return a.x < b.x || (a.x == b.x && a.y < b.y); }
bool operator >= (const Point& a, const Point& b) { return a.x >= b.x && a.y >= b.y; }
bool operator <= (const Point& a, const Point& b) { return a.x <= b.x && a.y <= b.y; }
bool operator == (const Point& a, const Point& b) { return dcmp(a.x-b.x) == && dcmp(a.y-b.y) == ; }
double Dot(Vector A, Vector B) { return A.x*B.x + A.y*B.y; }
double Length(Vector A) { return sqrt(Dot(A, A)); }
double Angle(Vector A, Vector B) { return acos(Dot(A, B) / Length(A) / Length(B)); }
double Cross(Vector A, Vector B) { return A.x*B.y - A.y*B.x; }
Vector VectorUnit(Vector x){ return x / Length(x);}
Vector Normal(Vector x) { return Point(-x.y, x.x) / Length(x);}
double angle(Vector v) { return atan2(v.y, v.x); } bool SegmentIntersection(Point A,Point B,Point C,Point D) {
return max(A.x,B.x) >= min(C.x,D.x) &&
max(C.x,D.x) >= min(A.x,B.x) &&
max(A.y,B.y) >= min(C.y,D.y) &&
max(C.y,D.y) >= min(A.y,B.y) &&
dcmp(Cross(C-A,B-A)*Cross(D-A,B-A)) <= &&
dcmp(Cross(A-C,D-C)*Cross(B-C,D-C)) <= ;
}
Vector Rotate(Point P,Vector A,double rad){ //以P为基准点把向量A旋转rad
return Vector(P.x+A.x*cos(rad)-A.y*sin(rad),P.y+A.x*sin(rad)+A.y*cos(rad));
} struct node {
char id;
int cnt;
Line line[];
vector<char> inter;
}poly[];
int cmp(node ka,node kb) { return ka.id < kb.id; } int main()
{
char ss[],shape[];
int tot = ,i,j,e,k;
while(scanf("%s",ss)!=EOF)
{
if(ss[] == '.') break;
if(ss[] != '-') {
poly[++tot].id = ss[];
scanf("%s",shape);
if(shape[] == 't') { //triangle
poly[tot].cnt = ;
Point P[];
for(i=;i<;i++) scanf(" (%lf,%lf)",&P[i].x,&P[i].y);
for(i=;i<;i++) poly[tot].line[i] = Line(P[i],P[(i+)%]-P[i]);
}
else if(shape[] == 's') { //square
poly[tot].cnt = ;
Point A,B,C,D;
scanf(" (%lf,%lf)",&A.x,&A.y);
scanf(" (%lf,%lf)",&C.x,&C.y);
B = Rotate(A,C-A,pi*0.25); B = A + (B-A)/sqrt(2.0);
D = C + (A-B);
poly[tot].line[] = Line(A,B-A), poly[tot].line[] = Line(B,C-B);
poly[tot].line[] = Line(C,D-C), poly[tot].line[] = Line(D,A-D);
}
else if(shape[] == 'r') { //rectangle
poly[tot].cnt = ;
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);
D = A + (C-B);
poly[tot].line[] = Line(A,B-A), poly[tot].line[] = Line(B,C-B);
poly[tot].line[] = Line(C,D-C), poly[tot].line[] = Line(D,A-D);
}
else if(shape[] == 'l') { //line
poly[tot].cnt = ;
Point A,B;
scanf(" (%lf,%lf)",&A.x,&A.y);
scanf(" (%lf,%lf)",&B.x,&B.y);
poly[tot].line[] = Line(A,B-A);
}
else if(shape[] == 'p') { //polygon
scanf("%d",&poly[tot].cnt);
Point P[];
for(i=;i<poly[tot].cnt;i++) {
scanf(" (%lf,%lf)",&P[i].x,&P[i].y);
if(i >= ) poly[tot].line[i-] = Line(P[i-],P[i]-P[i-]);
}
poly[tot].line[i-] = Line(P[i-],P[]-P[i-]);
}
}
else //processing...
{
for(i=;i<=tot;i++) //处理第i个多边形
{
poly[i].inter.clear();
for(e=;e<poly[i].cnt;e++) //枚举每条边
{
for(j=;j<=tot;j++) //枚举别的多边形
{
if(i == j) continue;
for(k=;k<poly[j].cnt;k++) //枚举别的多边形的每条边
{
Point A = poly[i].line[e].p, B = poly[i].line[e].p+poly[i].line[e].v;
Point C = poly[j].line[k].p, D = poly[j].line[k].p+poly[j].line[k].v;
if(SegmentIntersection(A,B,C,D))
{
poly[i].inter.push_back(poly[j].id);
break;
}
}
}
}
sort(poly[i].inter.begin(),poly[i].inter.end());
poly[i].inter.erase(unique(poly[i].inter.begin(),poly[i].inter.end()),poly[i].inter.end());
}
sort(poly+,poly+tot+,cmp);
for(i=;i<=tot;i++) {
printf("%c",poly[i].id);
int sz = poly[i].inter.size();
if(sz == )
puts(" has no intersections");
else {
printf(" intersects with ");
if(sz == )
printf("%c\n",poly[i].inter[]);
else if(sz == )
printf("%c and %c\n",poly[i].inter[],poly[i].inter[]);
else {
for(j=;j<sz-;j++) printf("%c, ",poly[i].inter[j]);
printf("and %c\n",poly[i].inter[j]);
}
}
}
puts("");
tot = ;
}
}
return ;
}