hdu 4613 Points<计算几何>

链接：http://acm.hdu.edu.cn/showproblem.php?pid=4613

题意： 判断一个集合中的点能不能由另一个集合中的点，通过平移，旋转，放缩得到~

思路：先求出集合中的点的凸包，然后枚举每一条边作为起点 ，看原集合中的点能否与要比较的集合中的点一一对应~

 #include <iostream>

 #include <cstdio>

 #include <algorithm>

 #include <functional>

 #include <utility>

 #include <cstring>

 #include <cmath>

 #include <complex>

 using namespace std;

 const int maxn = ;

 typedef complex<double> point;

 #define X real()

 #define Y imag()

 point p[maxn],s[maxn], tp[maxn],ts[maxn];

 double ang;

 int cnttp,cntts;

 int n,m,M,T;

 const double eps = 1e-;

 int sign(double x)

 {

     if(x>eps)return ;

     if( fabs(x)>eps )return -;

     return ;

 }

 bool cmp(const point& p1,const point& p2)

 {

     if( sign(p1.X-p2.X)== ) return ( sign( p1.Y-p2.Y)< );

     return sign( p1.X-p2.X)<;

 }

 double det(const point &p1,const point& p2,const point& org)

 {

     return (p1.X - org.X) * (p2.Y - org.Y) - (p1.Y - org.Y) * (p2.X - org.X);

 }

 void graham(int n,point *p,int& s,point *ch)

 {

     sort(p,p + n,cmp);

     int i,s2;

     ch[] = p[];s = ;

     for(i = ;i < n;i++) {

         while(s >  && det(p[i],ch[s - ],ch[s - ])<eps)s--;

         ch[s++] = p[i];

     }

     s2 = s;

     for(int i = n - ;i>=;i--) {

         while(s>s2 && det(p[i],ch[s - ],ch[s - ])<eps)s--;

         ch[s++] = p[i];

     }

     s--;

 }

 double getAngle(const point& p1,const point& p2)

 {

     double dot = p1.X * p2.X + p1.Y * p2.Y;

     dot /= abs(p1) * abs(p2);

     return dot;

 }

 bool check(const point& org,const point& trans)

 {

     for(int i = ;i<m;i++) {

         if(!binary_search(p,p + n,(s[i] - org) * trans + tp[],cmp))return false;

     }

     return true;

 }

 void gao()

 {

     scanf("%d",&m);

     for(int i =  ;i<m;i++) {

         scanf("%lf%lf",&s[i].X,&s[i].Y);

     }

     if(n!=m) {puts("No");return;}

     if(n<=){puts("Yes");return;}

     graham(m,s,cntts,ts);

     double sang;

     point org,trans;

     point A,B,C;

     for(int k=; k<=; ++ k){

         for(int i = ;i<m;i++)

             s[i].X = -s[i].X;

         for(int i = ;i<cntts;i++)

             ts[i].X = -ts[i].X;

         for(int i = ;i<cntts;i++) {

             B = ts[i];

             A = ts[(cntts + i - ) % cntts];

             C = ts[(i + ) % cntts];

             sang = getAngle(A - B,C - B);

             if(fabs(sang - ang)<eps) {

                 org = B;

                 trans =  (tp[] - tp[]) / (A - B);

                 if(check(org,trans)) {

                     puts("Yes");

                     return;

                 }

                 trans = (tp[] - tp[]) / (C - B);

                 if(check(org,trans)) {

                     puts("Yes");

                     return;

                 }

             }

         }

     }

     puts("No");

     return;

 }

 int main()

 {

     scanf("%d",&T);

     while(T--) {

         scanf("%d",&n);

         for(int i =;i<n;i++) {

             scanf("%lf%lf", &p[i].X, &p[i].Y);

         }

         if(n>) {

             graham(n,p,cnttp,tp);

             ang = getAngle(tp[] - tp[],tp[cnttp - ] - tp[]);

         }

         scanf("%d",&M);

         for(int i = ;i<M;i++)

             gao();

         puts("");

     }

     return ;

 }