1.AtCoder Beginner Contest 207 Congruence Points

 

 大意：给出两个集合，能否通过旋转和平移A集合中的点使它们与B集合中的点完全重合？

 题解：找出每个集合的重心，然后将重心移动到原点，那么就只需要考虑能否通过旋转使他们重合。找到A集合和B集合中到原点距离相等的两个点，求出需要旋转的角度，再暴力将A集合中的每个点旋转，判断是否能与B集合完全重合。

#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
#define ll long long

const int maxn=120; 
const double esp=1e-9;

int n,na,nb;
int a[maxn],b[maxn],c[maxn],d[maxn];
int x,y,xx,yy,sum;

double pf(double x){
    return x*x;
}

int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i]>>b[i];
        a[i]*=n; b[i]*=n;
    } 
    for(int i=1;i<=n;i++){
        cin>>c[i]>>d[i];
        c[i]*=n; d[i]*=n;
    } 
    for(int i=1;i<=n;i++) sum+=a[i];
    x=sum/n; sum=0;
    for(int i=1;i<=n;i++) sum+=b[i];
    y=sum/n; sum=0;
    for(int i=1;i<=n;i++) sum+=c[i];
    xx=sum/n; sum=0;
    for(int i=1;i<=n;i++) sum+=d[i];
    yy=sum/n; sum=0;
    for(int i=1;i<=n;i++){
        a[i]-=x; b[i]-=y;
        c[i]-=xx; d[i]-=yy;
        if(a[i]!=0){
            na=a[i];nb=b[i];
        }
    }
    for(int i=1;i<=n;i++){
        if(fabs(pf(c[i])+pf(d[i])-pf(na)-pf(nb))<=esp){
            double ang=atan2(d[i],c[i])-atan2(nb,na);
            bool p=1;
            for(int j=1;j<=n;j++){
                double nowa=a[j]*cos(ang)-b[j]*sin(ang);
                double nowb=a[j]*sin(ang)+b[j]*cos(ang);
                bool v=0;
                for(int k=1;k<=n;k++){
                    if(fabs(nowa-c[k])<=esp&&fabs(nowb-d[k])<=esp){
                        v=1; break;
                    }
                }
                p&=v;
            }
            if(p){
                cout<<"Yes"<<endl; return 0;
            }
        }
    }
    cout<<"No"<<endl;
    return 0;
}

View Code