本文主要是介绍hdu 2826 计算几何，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
http://acm.hdu.edu.cn/showproblem.php?pid=2826
题意：判断两个多边形相似
这个题目数据其弱无比，看了discuss里有人给的代码，根本就是错的。
相似要考虑 1.旋转 2.缩放 3.对称 几种情况， discuss里那个就没考虑对称。 我试了一下不光是不考虑对称能过，代码里连旋转都不考虑也可以过
#include<stdio.h>
#include<string.h>
#include<ctype.h>
#include<math.h>
#include<string>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<algorithm>
#include<ctime>
using namespace std;
void fre(){freopen("t.txt","r",stdin);}
#define ls o<<1
#define rs o<<1|1
#define MS(x,y) memset(x,y,sizeof(x))
typedef long long LL;
typedef unsigned long long UL;
typedef unsigned int UI;
const int INF = 1<<30;
const double eps = 1e-8;
const int MAXN = 200010;
const double pi = acos(-1.0);struct Point
{int x,y;
}p[305];
struct Line
{Point s,e;LL len;void get_len2(){len = (e.x-s.x)*(e.x-s.x) + (e.y-s.y)*(e.y-s.y);}double get_ang(Line b){double a1 = atan2(b.s.y-b.e.y,b.s.x-b.e.x);double a2 = atan2(e.y-s.y,e.x-s.x);double a3 = a1-a2;while(a3 < 0) a3+=2*pi;if(a3 > pi) a3 = 2*pi - a3;return a3;}
}l1[305],l2[305];
int n;
double ang1[305],ang2[305];
int main()
{//fre();while(~scanf("%d",&n)){for(int i = 0; i < n; ++i)scanf("%d%d",&p[i].x,&p[i].y);l1[0] = (Line){p[n-1],p[0]};l1[0].get_len2();for(int i = 1; i < n; ++i){l1[i] = (Line){p[i-1],p[i]};l1[i].get_len2();ang1[i] = l1[i].get_ang(l1[i-1]);}ang1[0] = l1[0].get_ang(l1[n-1]);for(int i = 0; i < n; ++i)scanf("%d%d",&p[i].x,&p[i].y);l2[0] = (Line){p[n-1],p[0]};l2[0].get_len2();for(int i = 1; i < n; ++i){l2[i] = (Line){p[i-1],p[i]};l2[i].get_len2();ang2[i] = l2[i].get_ang(l2[i-1]);}ang2[0] = l2[0].get_ang(l2[n-1]);bool flag = 0;int j;for(int i = 0; i < n && !flag; ++i){if(fabs(ang1[i] - ang2[0]) > eps) continue;//把continue改成break， 也就是直接无视旋转，都可以ACdouble k = 1.0*l1[i].len / l2[0].len;for(j = 1; j < n; ++j){if(fabs(1.0*l1[(i+j)%n].len / l2[j].len - k) > eps) break;if(fabs(ang1[(i+j)%n] - ang2[j]) > eps) break;}if(j == n) flag = 1;}for(int i = 0; i < n && !flag; ++i)//考虑对称，上面是两个都逆时针，这里是一个顺时针一个逆时针，去掉也能AC{if(fabs(ang1[i+1] - ang2[0]) > eps) continue;double k = 1.0*l1[i].len / l2[0].len;for(j = 1; j < n; ++j){if(fabs(1.0*l1[(i-j+n)%n].len / l2[j].len - k) > eps) break;if(fabs(ang1[(i-j+n+1)%n] - ang2[j]) > eps) break;}if(j == n) flag = 1;}if(flag) printf("Yes\n");else printf("No\n");}}
这篇关于hdu 2826 计算几何的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
