题意是判断多边形是否相交
主要的思路就是判断每一个点是否在另外的多变形内
判断一个点是否在另一个多边形内主要思路是:
判断的那个点向左边做射线,如果射线与多边形的交点为奇数个则在多边形内,偶数个则不在,其中有特殊情况:
1.如果判断的点与所要判断的边在平行且在所要判断的边上,则在多边形上
2.如果向左做射线恰好在某一点上,不特殊处理会计算两次,因为在两条边上,判断射线与多变形的交点数目,所以要在一个情况下忽略
3.就是判断点是否在多边形的左边了
but:WA了好久因为一个多边形可能包涵另一个多边形所以要全部遍历^!!!
#include <iostream> #include <cstdio> #include <cstdlib> #include <algorithm> #include <map> #include <cmath> #include <cstring> #include <string> #include <queue> #include <stack> #include <cctype> #include <set> #define ALL(x) x.begin(),x.end() #define INS(x) inserter(x,x.begin()) const int maxn = 10005; typedef long long LL; struct Point{ double x,y; }; using namespace std; Point point[12][22]; int t[12]; bool flag[21][21]; //参数： // POINT p 指定的某个点 // LPPOINT ptPolygon 多边形的各个顶点坐标（首末点可以不一致） // int nCount 多边形定点的个数 bool PtInPolygon (Point p, int num) { int nCross = 0; for(int i = 0; i < t[num]; i++){ Point p1 = point[num][i]; int tt = (i+1) % t[num]; Point p2 = point[num][tt]; double x1 = min(p1.x,p2.x); double x2 = max(p1.x,p2.x); double y1 = min(p1.y,p2.y); double y2 = max(p1.y,p2.y); if((p.y-p1.y)*(p.x-p2.x) == (p.y-p2.y) * (p.x - p1.x)){ if(p.x >= x1 && p.x <= x2 && p.y >= y1 && p.y <= y2) return true; continue; } if(p.y < y1) continue; if(p.y > y2 || abs(p.y-y2) < 10e-6) continue; double x = (p.y - p1.y) * (p2.x - p1.x) / (p2.y - p1.y) + p1.x; if ( x > p.x ) nCross++; } return (nCross % 2 == 1); } int main() { #ifndef ONLINE_JUDGE freopen("in.in","r",stdin); #endif int tt; cin >> tt; for(int cas = 1;cas <= tt;cas++){ int n; cin >> n; memset(flag,0,sizeof(flag)); for(int i = 0;i < n;i++){ cin >> t[i]; for(int j = 0;j < t[i];j++){ int tmp1,tmp2; char ch; cin >> tmp1 >> ch >> tmp2; point[i][j].x = tmp1; point[i][j].y = tmp2; } } for(int i = 0;i < n;i++){ for(int j = 0;j < n;j++){ if(i != j){ bool mark = 0; for(int k = 0;k < t[i];k++){ if(PtInPolygon(point[i][k],j)){ mark = 1; break; } } if(mark){ flag[i][j] = flag[j][i] = 1; } } } } bool aflag = 1; cout << "Data Set #" << cas << endl; for(int i = 0;i < n;i++){ for(int j = 0;j < n;j++){ if(flag[i][j]){ flag[i][j] = flag[j][i] = 0; aflag = 0; cout << i+1 << " " << j+1<< endl; } } } if(aflag) cout << "no collisions" << endl; } return 0; }
测试用例:
14 2 4 0,0 1,0 1,1 0,1 4 2,2 3,2 3,3 2,3 4 3 2,1 1,2 2,3 3 2,1 3,2 2,3 5 2,0 4,2 2,4 5,4 5,0 4 3,3 1,3 1,5 3,5 1 3 0,0 1,1 1,0 3 3 0,0 1,1 2,0 3 2,0 0,0 1,1 3 4,4 3,3 5,4 2 3 0,0 1,1 2,0 3 4,4 3,3 5,4 10 4 1,1 1,5 5,5 5,1 4 2,4 2,2 4,2 4,4 4 3,2 2,2 2,4 3,4 4 3,4 4,4 4,2 3,2 8 1,5 1,1 3,1 3,2 2,2 2,4 3,4 3,5 8 5,5 5,1 3,1 3,2 4,2 4,4 3,4 3,5 8 5,5 3,5 3,4 2,4 2,2 3,2 3,1 5,1 8 1,5 3,5 3,4 4,4 4,2 3,2 3,1 1,1 3 1,5 1,1 2,3 3 4,3 5,5 5,1 2 7 1,1 1,5 4,5 2,4 4,3 2,2 4,1 7 6,5 5,5 3,4 5,3 3,2 5,1 6,1 3 3 0,0 100,100 50,49 3 1,1 2,0 1,0 3 2,1 3,2 3,1 3 5 1,2 2,5 3,5 5,2 4,1 5 7,2 8,3 7,5 10,5 10,2 4 0,0 0,75 80,5 99,1 2 4 4,2 3,3 4,5 5,3 4 7,3 5,0 2,3 4,6 2 4 4,2 3,3 4,5 5,3 4 4,6 2,3 5,0 7,3 2 4 5,3 4,5 3,3 4,2 4 4,6 2,3 5,0 7,3 2 4 5,3 4,5 3,3 4,2 4 7,3 5,0 2,3 4,6 2 20 0,0 9,0 9,11 0,11 0,2 7,2 7,9 2,9 2,4 5,4 5,5 3,5 3,8 6,8 6,3 1,3 1,10 8,10 8,1 0,1 4 4,6 4,7 5,7 5,6
ans:
Data Set #1 no collisions Data Set #2 1 2 1 4 2 4 3 4 Data Set #3 no collisions Data Set #4 1 2 Data Set #5 no collisions Data Set #6 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 2 3 2 4 2 5 2 6 2 7 2 8 2 9 2 10 3 4 3 5 3 6 3 7 3 8 3 9 4 5 4 6 4 7 4 8 4 10 5 6 5 7 5 8 5 9 6 7 6 8 6 10 7 8 7 9 7 10 8 9 8 10 Data Set #7 no collisions Data Set #8 1 2 Data Set #9 1 3 2 3 Data Set #10 1 2 Data Set #11 1 2 Data Set #12 1 2 Data Set #13 1 2 Data Set #14 no collisions