POJ_3449
这个题目由于图形很少，思路还是很直接的，暴力就可以了，枚举任意两个图形，并枚举两个图形间所有线段的位置关系，如果存在两条线段相交，那么这两个图形就是相交的。
这个题的输入输出比较恶心，此外，对于正方形已知一对点求另一对点时可以用向量的旋转来求，首先求得正方形中心的坐标，然后将中心到两个点的连线看作两个向量，将这两个向量各旋转90度就可以得到中心到另外两个点的向量，进而就可以求得另外两个点的坐标了。向量的旋转可以参考矩阵运算中的一些内容：http://www.matrix67.com/blog/archives/276/。
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define MAXD 30
#define zero 1e-8
char b[110];
int N, name[MAXD], vn[MAXD], g[MAXD][MAXD], n[MAXD], vis[MAXD];
double x[MAXD][MAXD], y[MAXD][MAXD];
int cmp(const void *_p, const void *_q)
{
int *p = (int *)_p;
int *q = (int *)_q;
return *p - *q;
}
void input()
{
int i, j, k;
name[N] = b[0];
scanf("%s", b);
if(strcmp(b, "square") == 0)
{
vn[N] = 4;
scanf("%s", b);
sscanf(b, "(%lf,%lf)", &x[N][0], &y[N][0]);
scanf("%s", b);
sscanf(b, "(%lf,%lf)", &x[N][2], &y[N][2]);
double dx, dy, x0, y0;
x0 = (x[N][0] + x[N][2]) / 2, y0 = (y[N][0] + y[N][2]) / 2;
dx = x[N][0] - x0, dy = y[N][0] - y0;
x[N][1] = x0 - dy, y[N][1] = y0 + dx;
dx = x[N][2] - x0, dy = y[N][2] - y0;
x[N][3] = x0 - dy, y[N][3] = y0 + dx;
x[N][4] = x[N][0], y[N][4] = y[N][0];
}
else if(strcmp(b, "rectangle") == 0)
{
vn[N] = 4;
for(i = 0; i < 3; i ++)
{
scanf("%s", b);
sscanf(b, "(%lf,%lf)", &x[N][i], &y[N][i]);
}
x[N][3] = x[N][0] + (x[N][2] - x[N][1]), y[N][3] = y[N][0] + (y[N][2] - y[N][1]);
x[N][4] = x[N][0], y[N][4] = y[N][0];
}
else if(strcmp(b, "line") == 0)
{
vn[N] = 1;
for(i = 0; i < 2; i ++)
{
scanf("%s", b);
sscanf(b, "(%lf,%lf)", &x[N][i], &y[N][i]);
}
}
else if(strcmp(b, "triangle") == 0)
{
vn[N] = 3;
for(i = 0; i < 3; i ++)
{
scanf("%s", b);
sscanf(b, "(%lf,%lf)", &x[N][i], &y[N][i]);
}
x[N][3] = x[N][0], y[N][3] = y[N][0];
}
else
{
scanf("%d", &vn[N]);
for(i = 0; i < vn[N]; i ++)
{
scanf("%s", b);
sscanf(b, "(%lf,%lf)", &x[N][i], &y[N][i]);
}
x[N][vn[N]] = x[N][0], y[N][vn[N]] = y[N][0];
}
}
int init()
{
int i, j, k;
for(N = 0; ; N ++)
{
scanf("%s", b);
if(b[0] == '.')
return 0;
if(b[0] == '-')
break;
input();
}
return 1;
}
double fabs(double x)
{
return x < 0 ? -x : x;
}
double dcmp(double x)
{
if(fabs(x) < zero)
return 0;
if(x < 0)
return -1;
return 1;
}
double det(double x1, double y1, double x2, double y2)
{
return x1 * y2 - x2 * y1;
}
int inseg(double x, double y, double x1, double y1, double x2, double y2)
{
if(fabs(x1 - x2) < fabs(y1 - y2))
{
if(dcmp((y1 - y) * (y2 - y)) <= 0)
return 1;
}
else
{
if(dcmp((x1 - x) * (x2 - x)) <= 0)
return 1;
}
return 0;
}
int check(double x1, double y1, double x2, double y2, double x3, double y3, double x4, double y4)
{
double t1, t2, t3, t4;
t1 = det(x2 - x1, y2 - y1, x3 - x1, y3 - y1);
t2 = det(x2 - x1, y2 - y1, x4 - x1, y4 - y1);
t3 = det(x4 - x3, y4 - y3, x1 - x3, y1 - y3);
t4 = det(x4 - x3, y4 - y3, x2 - x3, y2 - y3);
if(dcmp(t1) == 0 && inseg(x3, y3, x1, y1, x2, y2))
return 1;
if(dcmp(t2) == 0 && inseg(x4, y4, x1, y1, x2, y2))
return 1;
if(dcmp(t3) == 0 && inseg(x1, y1, x3, y3, x4, y4))
return 1;
if(dcmp(t4) == 0 && inseg(x2, y2, x3, y3, x4, y4))
return 1;
if(dcmp(t1) * dcmp(t2) < 0 && dcmp(t3) * dcmp(t4) < 0)
return 1;
return 0;
}
void calculate(int i, int j)
{
int p, q;
for(p = 0; p < vn[i]; p ++)
for(q = 0; q < vn[j]; q ++)
if(check(x[i][p], y[i][p], x[i][p + 1], y[i][p + 1], x[j][q], y[j][q], x[j][q + 1], y[j][q + 1]))
{
g[i][n[i] ++] = name[j];
g[j][n[j] ++] = name[i];
return ;
}
}
void printresult(int k)
{
int i, j;
if(n[k] == 0)
printf("%c has no intersections\n", name[k]);
else if(n[k] == 1)
printf("%c intersects with %c\n", name[k], g[k][0]);
else if(n[k] == 2)
printf("%c intersects with %c and %c\n", name[k], g[k][0], g[k][1]);
else
{
printf("%c intersects with ", name[k]);
for(j = 0; j < n[k] - 1; j ++)
printf("%c, ", g[k][j]);
printf("and %c\n", g[k][n[k] - 1]);
}
}
void solve()
{
int i, j, k, t;
memset(n, 0, sizeof(n));
for(i = 0; i < N; i ++)
for(j = i + 1; j < N; j ++)
calculate(i, j);
memset(vis, 0, sizeof(vis));
for(i = 0; i < N; i ++)
{
t = 128;
for(j = 0; j < N; j ++)
if(!vis[j] && name[j] < t)
k = j, t = name[j];
vis[k] = 1;
qsort(g[k], n[k], sizeof(g[k][0]), cmp);
printresult(k);
}
}
int main()
{
while(init())
{
solve();
printf("\n");
}
return 0;
}