Geometric Shapes - POJ 3449（多邊形相交）

題目大意：給一些幾何圖形的編號，求出來這些圖形都和那些相交。

?

分析：輸入的正方形對角線上的兩個點，所以需要求出來另外兩個點，公式是：

x2:=(x1+x3+y3-y1)/2; y2:=(y1+y3+x1-x3)/2;

x4:=(x1+x3-y3+y1)/2; y4:=(y1+y3-x1+x3)/2;

這個是可以推倒出來的，有興趣的可以推一下，給的矩形三個點，是按照順序給的，求出來第四個點即可，比較容易求，x4=x1-x2+x3， y4=y1-y2+y3

別的圖形的點也都是按照順序給的，兩個圖形如果相交一定是邊的相交，一個圖形把另一個包含不算相交。所以處理完輸入輸出，還是比較容易做的。

?

代碼如下：

========================================================================================================================

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<algorithm>
using namespace std;const int MAXN = 26;
const double EPS = 1e-8;int Sign(double t)
{if(t > EPS)return 1;if(fabs(t) < EPS)return 0;return -1;
}
struct Point
{double x, y;Point(double x=0, double y=0):x(x),y(y){}Point operator - (const Point &tmp)const{return Point(x-tmp.x, y-tmp.y);}double operator ^(const Point &tmp)const{return x*tmp.y - y*tmp.x;}
};
struct Segment
{Point S, E;Segment(Point S=0, Point E=0):S(S), E(E){}bool Intersect(const Segment &tmp)const{int t1 = Sign((S-E)^(tmp.S-E));int t2 = Sign((S-E)^(tmp.E-E));return abs(t1+t2) != 2;}
};
struct Shapes
{Segment sg[MAXN];int N;
};
bool Find(int u, int v, Shapes a[])
{for(int i=0; i<a[u].N; i++)for(int j=0; j<a[v].N; j++){if(a[u].sg[i].Intersect(a[v].sg[j]) && a[v].sg[j].Intersect(a[u].sg[i]))return true;}return false;
}
void Link(Shapes a[], int k, Point p[])
{int i, N=a[k].N;p[N] = p[0];for(i=1; i<=N; i++)a[k].sg[i-1] = Segment(p[i-1], p[i]);
}
int main()
{char Id[MAXN], s[MAXN], s1[MAXN], s2[MAXN];Shapes a[MAXN];Point p[MAXN];memset(a, 0, sizeof(a));while(scanf("%s", Id) != EOF && Id[0] != '.'){if(Id[0] == '-'){for(int i=0; i<MAXN; i++){if(a[i].N){///如果這個符號的形狀存在int ans[MAXN], k=0;for(int j=0; j<MAXN; j++){if(!a[j].N || i==j)continue;if(Find(i, j, a) == true)ans[k++] = j;}if(k == 1)printf("%c intersects with %c\n", i+'A', ans[0]+'A');else if(k == 0)printf("%c has no intersections\n", i+'A');else{printf("%c intersects with %c", i+'A', ans[0]+'A');for(int t=1; t<k-1; t++)printf(", %c", ans[t]+'A');if(k == 2)printf(" and %c\n", ans[k-1]+'A');elseprintf(", and %c\n", ans[k-1]+'A');}}}printf("\n");memset(a, 0, sizeof(a));}else{scanf("%s", s);int k = Id[0] - 'A';if(strcmp(s, "square") == 0){///正方形a[k].N = 4;scanf("%s%s", s1, s2);sscanf(s1, "(%lf,%lf)", &p[0].x, &p[0].y);sscanf(s2, "(%lf,%lf)", &p[2].x, &p[2].y);p[1].x = (p[0].x+p[2].x + p[2].y-p[0].y)/2;p[1].y = (p[0].x-p[2].x + p[0].y+p[2].y)/2;p[3].x = (p[0].x+p[2].x + p[0].y-p[2].y)/2;p[3].y = (p[2].x-p[0].x + p[0].y+p[2].y)/2;}else if(strcmp(s, "line") == 0){///直線a[k].N = 2;scanf("%s%s", s1, s2);sscanf(s1, "(%lf,%lf)", &p[0].x, &p[0].y);sscanf(s2, "(%lf,%lf)", &p[1].x, &p[1].y);}else if(strcmp(s, "rectangle") == 0){///長方形a[k].N = 4;for(int t=0; t<3; t++){scanf("%s", s1);sscanf(s1, "(%lf,%lf)", &p[t].x, &p[t].y);}p[3].x = p[0].x-p[1].x+p[2].x;p[3].y = p[0].y-p[1].y+p[2].y;}else if(strcmp(s, "triangle") == 0){///三角形a[k].N = 3;for(int t=0; t<3; t++){scanf("%s", s1);sscanf(s1, "(%lf,%lf)", &p[t].x, &p[t].y);}}else if(strcmp(s, "polygon") == 0){///多邊形scanf("%d", &a[k].N);for(int t=0; t<a[k].N; t++){scanf("%s", s1);sscanf(s1, "(%lf,%lf)", &p[t].x, &p[t].y);}}Link(a, k, p);}}return 0;
}

?