A题：因为数据量太小，所以直接暴力替换就好。。。。
#include #include #include #include
B题：数据只有100000，故可以直接用一个map记录每个点所在的区间标识。
#include #include #include #include
C题：直接暴力枚举旋转的可能性，因为每个点最多转3次，最后判断是不是正方形就行。
#include #include #include #include const int inf=9999999; using namespace std; struct node { int x; int y; }p[5][5],home[5]; long long d[8]; long long dis(node a,node b)//距离的平方 { return (long long)(a.x-b.x)*(a.x-b.x)+(long long)(a.y-b.y)*(a.y-b.y); } void solve() { int ans=inf; for(int i=0;i<4;i++) { for(int j=0;j<4;j++) { for(int k=0;k<4;k++) { for(int l=0;l<4;l++) { d[0]=dis(p[i][0],p[j][1]);//四边距离的平方 d[1]=dis(p[j][1],p[k][2]); d[2]=dis(p[k][2],p[l][3]); d[3]=dis(p[l][3],p[i][0]); d[4]=dis(p[i][0],p[k][2]);//对角线的平方 d[5]=dis(p[j][1],p[l][3]); sort(d,d+6); if(d[0]==0) continue; else if(d[0]==d[1]&&d[1]==d[2]&&d[2]==d[3]&&2*d[3]==d[4]&&d[4]==d[5])//判断是否为正方形 { ans=min(ans,i+j+k+l); } } } } } if(ans!=inf) printf("%d\n",ans); else printf("-1\n"); } int main() { int t; scanf("%d",&t); while(t--) { for(int i=0;i<4;i++) { scanf("%d%d",&p[0][i].x,&p[0][i].y); scanf("%d%d",&home[i].x,&home[i].y); int x=p[0][i].x-home[i].x; int y=p[0][i].y-home[i].y; p[1][i].x=home[i].x-y;//逆时针旋转90度 p[1][i].y=home[i].y+x; p[2][i].x=home[i].x-x; p[2][i].y=home[i].y-y; p[3][i].x=home[i].x+y; p[3][i].y=home[i].y-x; } solve(); } return 0; }
D题：用dp[i][0]表示第i位不是W，dp[i][1]表示第i位是W，这样转移方程就很容易出来了，具体见代码，记得dp[0]时的初始化
#include #include #include #include
