题意:n个点(n<=10),取出6个点,组成两个一样的三角形,一样的三角形定义为旋转,平移后一样
题解:直接枚举6个点,6个点取三角形,先判断是不是三角形,再判断点的顺序和边的大小
#include<stdio.h> #include<bitset> #include<iostream> #include<algorithm> #include<vector> #include<string.h> #define INF 0x3f3f3f3f #define maxn 15 using namespace std; struct node{ int x, y; node(){x=y=0;} node(int aa,int bb){x = aa,y = bb;} node(const node& rhx){x = rhx.x;y = rhx.y;} friend node operator - (const node& aa,const node& bb){return node(aa.x-bb.x, aa.y-bb.y);} friend node operator + (const node& aa,const node& bb){return node(aa.x+bb.x, aa.y+bb.y);} }a[maxn], c1[maxn], c2[maxn]; int t1[maxn], t2[maxn], ans, T, n, b[maxn], ca = 1; int dis(node &aa,node &bb){ return (aa.x-bb.x)*(aa.x-bb.x)+(aa.y-bb.y)*(aa.y-bb.y); } int cross(const node &aa,const node &bb){ return aa.x*bb.y-aa.y*bb.x; } int cmp(node &aa,node &bb){ if(aa.x == bb.x) return aa.y>bb.y; return aa.x<bb.x; } double area(node *c) { int area = 0; area += cross(c[1]-c[0], c[2]-c[0]); return area; } int check(){ if(cross(c1[0]-c1[1], c1[0]-c1[2]) == 0||cross(c2[0]-c2[1], c2[0]-c2[2]) == 0) return 0; if(area(c1)*area(c2) < 0){ swap(c1[0], c1[2]); } for(int i=0;i<3;i++){ t1[i] = dis(c1[i], c1[(i+1)%3]); t2[i] = dis(c2[i], c2[(i+1)%3]); } if((t1[0] == t2[0]&&t1[1] == t2[1]&&t1[2] == t2[2]) ||(t1[0] == t2[1]&&t1[1] == t2[2]&&t1[2] == t2[0]) ||(t1[0] == t2[2]&&t1[1] == t2[0]&&t1[2] == t2[1])) return 1; return 0; } int main(){ cin>>T; while(T--){ ans = 0; cin>>n; for(int i=0;i<n;i++) cin>>a[i].x>>a[i].y; int comb = (1<<6)-1, x, y; while(comb < (1<<n)){ int num = 0; for(int i=0;i<n;i++) if(comb&(1<<i)) b[num++] = i; int t = (1<<3)-1; while(t < (1<<6)){ int num1=0,num2=0; for(int i=0;i<6;i++) if(t&(1<<i)) c1[num1++] = a[b[i]]; else c2[num2++] = a[b[i]]; if(check()) ans++; x = t&-t;y = t+x; t = ((t&~y)/x>>1)|y; } x = comb&-comb;y = comb+x; comb = ((comb&~y)/x>>1)|y; } printf("Case %d: ", ca++); cout<<ans<<endl; } return 0; }