原题链接
考察:暴力枚举
思路:
??记这道题的唯一意义是:
逆时针旋转90度后x‘=-y,y=x
逆时针旋转180度后x‘=-x,y=-y
逆时针旋转270度后x‘=y,y=-x
Code
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
const int N = 110,M = 5;
struct Node{
int x,y,a,b;
Node& operator=(const Node& n){
this->x = n.x,this->b = n.b;
this->y = n.y,this->a = n.a;
return *this;
}
bool operator<(const Node& s){
if(s.x==this->x) return this->y<s.y;
return this->x<s.x;
}
}node[N],nodes[M],bn[M];
int n,cnt;
Node get(int x,int y,int a,int b)
{
int nx = b-y+a,ny = x-a+b;
return {nx,ny,a,b};
}
long long Dist(Node a,Node b)
{
return (1ll*a.x-b.x)*(1ll*a.x-b.x)+(LL)(a.y-b.y)*(a.y-b.y);
}
bool check()
{
for(int i=1;i<=4;i++) bn[i] = nodes[i];
sort(nodes+1,nodes+5);
LL dmax = Dist(nodes[1],nodes[4]);
LL d1 = Dist(nodes[1],nodes[2]),d2 = Dist(nodes[1],nodes[3]);
if(d1!=d2||d1+d2!=dmax||!d1||!d2||!dmax) return 0;
d1 = Dist(nodes[3],nodes[4]),d2 = Dist(nodes[2],nodes[4]);
if(d1!=d2||d1+d2!=dmax||!d1||!d2||!dmax) return 0;
d1 = Dist(nodes[2],nodes[3]);
if(dmax!=d1||!d1||!dmax) return 0;
return 1;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=4*n;i++)
{
int x,y,a,b;
scanf("%d%d%d%d",&x,&y,&a,&b);
node[i] = {x,y,a,b};
}
for(int i=1;i<=n;i++)
{
int res = 0x3f3f3f3f;
cnt = 0;
Node t1 = node[(i-1)*4+1];
for(int a=0;a<4;a++)
{//第一个点旋转a次
if(a>=res) continue;
if(a) t1 = get(t1.x,t1.y,t1.a,t1.b);
nodes[1] = t1;
Node t2 = node[(i-1)*4+2];
for(int b=0;b<4;b++)
{
if(a+b>=res) continue;
if(b) t2 = get(t2.x,t2.y,t2.a,t2.b);
nodes[2] = t2;
Node t3 = node[(i-1)*4+3];
for(int c=0;c<4;c++)
{
if(a+b+c>=res) continue;
if(c) t3 = get(t3.x,t3.y,t3.a,t3.b);
nodes[3] = t3;
Node t4 = node[(i-1)*4+4];
for(int d=0;d<4;d++)
{
if(a+b+c+d>=res) continue;
if(d) t4 = get(t4.x,t4.y,t4.a,t4.b);
nodes[4] = t4;
if(check()) res = a+b+c+d;
for(int k=1;k<=4;k++) nodes[k] = bn[k];
}
}
}
}
if(res!=0x3f3f3f3f) printf("%d\n",res);
else puts("-1");
}
return 0;
}