首页 > 试题广场 > 整理房间
[编程题]整理房间
  • 热度指数:3322 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
又到了周末,小易的房间乱得一团糟。
他希望将地上的杂物稍微整理下,使每团杂物看起来都紧凑一些,没有那么乱。
地上一共有n团杂物,每团杂物都包含4个物品。第i物品的坐标用(ai,bi)表示,小易每次都可以将它绕着(xi,yi)逆时针旋转,这将消耗他的一次移动次数。如果一团杂物的4个点构成了一个面积不为0的正方形,我们说它是紧凑的。
因为小易很懒,所以他希望你帮助他计算一下每团杂物最少需要多少步移动能使它变得紧凑。

输入描述:
第一行一个数n(1 <= n <= 100),表示杂物的团数。
接下来4n行,每4行表示一团杂物,每行4个数ai, bi,xi, yi, (-10<= xi, yi, ai, b<= 104),表示第i个物品旋转的它本身的坐标和中心点坐标。


输出描述:
n行,每行1个数,表示最少移动次数。
示例1

输入

4
1 1 0 0
-1 1 0 0
-1 1 0 0
1 -1 0 0
1 1 0 0
-2 1 0 0
-1 1 0 0
1 -1 0 0
1 1 0 0
-1 1 0 0
-1 1 0 0
-1 1 0 0
2 2 0 1
-1 0 0 -2
3 0 0 -2
-1 1 -2 0

输出

1
-1
3
3

说明

对于第一团杂物,我们可以旋转第二个或者第三个物品1次。
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <bitset>
#include <unordered_map>
#include <stack>
#include <queue>
#include <deque>
#include <limits.h>
#include <cstdio>
using namespace std;

struct Item{
    int a, b, x, y, state;
    Item(){
        state = 0;
    }

    void crot(){
        state = (state + 1) % 4;
        int dx = a-x, dy = b-y;
        a = x - dy;
        b = y + dx;
    }

    void input(){
        cin>>a>>b>>x>>y;
        state = 0;
    }

    bool operator ==(const Item &item2){
        return a==item2.a && b==item2.b;
    }

    Item operator +(const Item &it2){
        Item res;
        res.a = a + it2.a;
        res.b = b + it2.b;
        return res;
    }

    Item operator -(const Item &it2){
        Item res;
        res.a = a - it2.a;
        res.b = b - it2.b;
        return res;
    }

    static bool ortho(const Item &it1, const Item &it2){
        if(it1.a==0 && it1.b== 0) return 0;
        if(it2.a==0 && it2.b == 0) return 0;
        return it1.a * it2.a + it1.b * it2.b == 0;
    }
};

struct Pack{
    vector<Item> itemList;
    vector<Item*> itp;
    int step;

    Pack(){
        itemList = vector<Item>(4);
        itp = vector<Item*>(4, nullptr);
        for(int i=0; i<4; ++i) itp[i] = &itemList[i];
        step = INT_MAX;
    }

    void input(){
        for(int i=0; i<4;++i)
            itemList[i].input();
        step = INT_MAX;
    }

    bool isSqaure(){
        for(int i=1; i<4; ++i){
            if(i!=1) swap(itp[i], itp[1]);
            if(*itp[0]==*itp[1] || *itp[2]==*itp[3]) return 0;
            if(!(*itp[0] + *itp[1] == *itp[2] + *itp[3])) continue;
            if(!Item::ortho(*itp[0]- *itp[1], *itp[2] - *itp[3])) continue;
            if(Item::ortho(*itp[0]- *itp[2], *itp[0] - *itp[3])) return 1;
        }
        return 0;
    }

    void trySqaure(int rot_idx){
        for(int i=0; i<4; ++i){
            if(rot_idx == 0 && isSqaure()){
                int tmp_step = 0;
                for(int j=0; j<4; ++j) tmp_step += itemList[j].state;
                if(step > tmp_step) step = tmp_step;
            }
            if(rot_idx > 0) trySqaure(rot_idx - 1);
            itemList[rot_idx].crot();
        }
    }
};

int main()
{
    int n;
    cin>>n;
    Pack eRoom;
    for(int i=0; i<n; ++i){
        eRoom.input();
        eRoom.trySqaure(3);
        cout<<(eRoom.step > 16 ? -1: eRoom.step)<<endl;
    }
}

数据结构化的写法,清楚的话求点赞

发表于 2018-08-15 00:50:02 回复(1)
import java.util.Scanner;

class Point {
    int x1;
    int y1;
    int x;
    int y;

    Point(int x1, int y1, int x, int y) {
        this.x1 = x1;
        this.y1 = y1;
        this.x = x;
        this.y = y;
    }
}

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Point[][] points = new Point[n][4];
        int a, b, c, d;
        int[] reult = new int[n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < 4; j++) {
                a = sc.nextInt();
                b = sc.nextInt();
                c = sc.nextInt();
                d = sc.nextInt();
                points[i][j] = new Point(a, b, c, d);
            }
            reult[i] = moveIimes(points, i);
        }
        for (int i = 0; i < reult.length; i++) {
            System.out.println(reult[i]);
        }
    }

    //每个点有4中情况旋转0,1,2,3次,穷举
    private static int moveIimes(Point[][] pints, int i) {
        Point p1, p2, p3, p4;
        int count = 16;
        for (int j = 0; j < 4; j++) {
            //第一个点的
            p1 = rotate(pints[i][0], j);
            for (int k = 0; k < 4; k++) {
                p2 = rotate(pints[i][1], k);
                for (int l = 0; l < 4; l++) {
                    p3 = rotate(pints[i][2], l);
                    for (int m = 0; m < 4; m++) {
                        p4 = rotate(pints[i][3], m);
                        if (isSq(p1, p2, p3, p4)) {
                            count = Math.min(count, j + k + l + m);
                        }
                    }
                }
            }
        }
        return count == 16 ? -1 : count;
    }

    /**
     * @param p     原始点
     * @param times 旋转次数
     * @return 返回旋转后的点
     */
    private static Point rotate(Point p, int times) {
        int x = p.x1;
        int y = p.y1;
        int a = p.x;//中心点
        int b = p.y;
        for (int i = 1; i <= times; i++) {
            int tem = x;
            x = (b - y + a);
            y = (tem - a + b);
        }
        return new Point(x, y, a, b);
    }

    //判断四个点是否是正方形
    private static boolean isSq(Point p1, Point p2, Point p3, Point p4) {
        boolean rx = ((p1.x1) ^ (p2.x1) ^ (p3.x1) ^ (p4.x1)) == 0;//四个点的 x 坐标是否是两两相等
        boolean ry = ((p1.y1) ^ (p2.y1) ^ (p3.y1) ^ (p4.y1)) == 0;//四个点的 y 坐标是否是两两相等
        //是否是矩形
        if (!rx || !ry || rx && ry && (p1.x1 == p2.x1 && p1.x1 == p3.x1) ||
                rx && ry && (p1.y1 == p2.y1 && p1.y1 == p3.y1)) return false;
        //判断正方形
        int dx = Math.abs((p1.x1 - p2.x1) != 0 ? (p1.x1 - p2.x1) : (p1.x1 - p3.x1));
        int dy = Math.abs((p1.y1 - p2.y1) != 0 ? (p1.y1 - p2.y1) : (p1.y1 - p3.y1));
        return dx == dy;
    }

}
编辑于 2019-07-26 19:57:33 回复(3)
这种题真的很考验coding能力,参考热评的大佬,写的易于理解的版本,思路就是挨个点旋转,然后判定是否是正方形,写的代码和思路完全一致,很容易看懂。
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();

        int[][][] abxy=new int[n][4][4];
        for(int i=0;i<n;i++){
            for(int j=0;j<4;j++){
                abxy[i][j][0]=sc.nextInt();
                abxy[i][j][1]=sc.nextInt();
                abxy[i][j][2]=sc.nextInt();
                abxy[i][j][3]=sc.nextInt();
            }
        }
        for(int index=0;index<n;index++){
            int min=Integer.MAX_VALUE;
            for(int i=0;i<4;i++){
                for(int j=0;j<4;j++){
                    for(int k=0;k<4;k++){
                        for(int m=0;m<4;m++){
                            if(isSquare(rotate(abxy[index][0],i),rotate(abxy[index][1],j),rotate(abxy[index][2],k),rotate(abxy[index][3],m))){
                                min=Math.min(min,i+j+k+m);
                            }
                        }
                    }
                }
            }
            if(min==Integer.MAX_VALUE){
                min=-1;
            }
            System.out.println(min);
        }

    }
    //绕xy旋转count次 point长度为4,固定这个长度是因为这样在调用的时候比较方便      
       public static  int[] rotate(int[] point,int count){
        int[] res=new int[] {point[2]+point[3]-point[1], point[3]-point[2]+point[0],point[2],point[3]};
        if(count==0){
            return point;
        }else{
            return rotate(res,count-1);
        }
    }
    //判定正方形,一定要判定两个对角边是否相等
    public static  boolean isSquare(int[] point1,int[] point2,int[] point3,int[] point4){
        double[] sideLen=new double[]{distance(point1,point2),distance(point2,point3),distance(point3,point4),distance(point4,point1),distance(point1,point3),distance(point2,point4)};
        Arrays.sort(sideLen);
        return sideLen[0] != 0&&sideLen[0]==sideLen[1]&&sideLen[1]==sideLen[2]&&sideLen[2]==sideLen[3]&&sideLen[3]==sideLen[0]
                &&sideLen[4]==sideLen[5];
    }

    private static double distance(int[] fromPoint, int[] toPoint) {
        return Math.pow(fromPoint[0] - toPoint[0], 2)
                + Math.pow(fromPoint[1] - toPoint[1], 2);
    }
}

发表于 2019-08-02 11:15:51 回复(2)
  1. 如何判断四个点能否组成正方形: 假设四个点编号为[1, 2, 3, 4], 考虑正方形的对称性, 检查i) 1->2->3->4, ii) 1->3->2->4, iii) 1->2->4->3 这三种情况能否组成正方形即可. 确定顺序后四条边边长相等且对角线长度相等即可组成正方形.
  2. 如何绕将点p绕点c逆时针旋转90度: i) 将坐标原点移动至点c: p.x -= c.x, p.y -= c.y ii) 绕坐标原点逆时针旋转90度: p.x = -p.y, p.y=p.x. 可用极坐标证明上式. iii) 将坐标原点重新移回(0, 0): p.x += c.x, p.y += c.y
  3. 如何确定最小操作次数: 4团杂物每个有4种旋转情况, 将4^4 = 256种组合情况均枚举一遍即可.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Point{
public:
    int x, y;
    Point()=default;
    Point(int x, int y): x(x), y(y) {};

    bool operator== (const Point &a) const {
        return x == a.x && y == a.y;
    }

    void rotate(const Point &center) {
        x -= center.x;
        y -= center.y;
        swap(x, y);
        x = -x;
        x += center.x;
        y += center.y;
        return;
    }
};

int distance(const Point &a, const Point &b) {
    return (b.x - a.x) * (b.x - a.x) + (b.y - a.y) * (b.y - a.y);
}

bool is_square(const Point &a, const Point &b, const Point &c, const Point &d) {
    if(a == b || a == c || a == d || b == c || b == d || c == d)
        return false;

    // 1 2 3 4
    if(distance(a, b) == distance(b, c) && distance(b, c) == distance(c, d) &&
       distance(c, d) == distance(d, a) && distance(a, c) == distance(b, d))
        return true;

    // 1 2 4 3
    if(distance(a, b) == distance(b, d) && distance(b, d) == distance(d, c) &&
       distance(d, c) == distance(c, a) && distance(a, d) == distance(b, c))
        return true;

    // 1 4 2 3
    if(distance(a, d) == distance(d, b) && distance(d, b) == distance(b, c) &&
       distance(b, c) == distance(c, a) && distance(a, b) == distance(c, d))
        return true;

    return false;
}

void backtrack(const vector<Point> &points, const vector<Point> &centers, int pos, vector<Point> &curr, int ops, int &res) {
    if(curr.size() == 4) {
        if(is_square(curr[0], curr[1], curr[2], curr[3]))
            res = res == -1 ? ops : min(res, ops);
        return;
    }

    int local_op = 0, k = 0;
    auto p = points[pos];
    do {
        curr.push_back(p);
        backtrack(points, centers, pos+1, curr, ops+local_op, res);
        curr.pop_back();

        p.rotate(centers[pos]);
        local_op++;
        k++;
    } while(k < 4);

    return;
}

int main() {
    int n;
    cin >> n;
    int px, py, cx, cy;
    vector<Point> points(4), centers(4);
    for(int i = 0; i < n; i++) {
        for(int k = 0; k < 4; k++) {
            cin >> px >> py >> cx >> cy;
            points[k] = Point(px, py);
            centers[k] = Point(cx, cy);
        }
        int res = -1;
        vector<Point> curr;
        backtrack(points, centers, 0, curr, 0, res);
        cout << res << endl;
    }

    return 0;
}

编辑于 2019-08-27 10:27:10 回复(0)
枚举所有情况判断是否形成正方形
defchange(i, x, y):
    return[x +y -i[1], y -x +i[0]]
defdis(a, b):
    return(a[0] -b[0])**2+(a[1] -b[1])**2
defsquare(a, b, c, d):
    q =[dis(a, b), dis(a, c), dis(a, d), dis(b, c), dis(b, d), dis(c, d)]
    q.sort()
    ifq[0]!=0andq[0] ==q[1] andq[1] ==q[2] andq[2] ==q[3] andq[4] ==q[5]andq[4] ==2*q[3]:
        returnTrue
    returnFalse
 
n =int(raw_input().strip())
forw inrange(n):
    best =100
    p =[]
    fori inrange(4):
        a, b, x, y =map(int, raw_input().strip().split())
        temp1 =[[a, b]]
        forj inrange(3):
            temp1.append(change(temp1[-1], x, y))
        p.append(temp1)
     
    fori inrange(4):
        forj inrange(4):
            fork inrange(4):
                forl inrange(4):
                    ifsquare(p[0][i], p[1][j], p[2][k], p[3][l]):
                        best =min(best, i +j +k +l)
    ifbest ==100:
        best =-1
    printbest



发表于 2018-08-14 17:18:12 回复(2)
// 穷举
// 逆时针转四次就转回去了,所以每次直接修改原数组就可以了,不用定义另外的class
// 一定要注意计算距离的时候用long, 否则要溢出(算平方就行,不用开根号,所以没用double,于是遇到了溢出)
// 判断是否是正方形: 最短边有4条,最长边有2条
import java.io.*;
public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[][] points = new int[4][4];
        String[] strs;
        while(n-- >0){
            int cnt = Integer.MAX_VALUE;
            for(int i = 0; i < 4; i++){
                strs = br.readLine().trim().split(" ");
                points[i][0] = Integer.parseInt(strs[0]);
                points[i][1] = Integer.parseInt(strs[1]);
                points[i][2] = Integer.parseInt(strs[2]);
                points[i][3] = Integer.parseInt(strs[3]);
            }
            
            for(int i = 0; i < 4; i++){
                rotateCounterClockwise(points[0]);
                for(int j = 0; j < 4; j++){
                    rotateCounterClockwise(points[1]);
                    for(int k = 0; k < 4; k++){
                        rotateCounterClockwise(points[2]);
                        for(int l = 0; l < 4; l++){
                            rotateCounterClockwise(points[3]);
                            if(isSquare(points)){
                                int c = (i+1)%4+(j+1)%4+(k+1)%4+(l+1)%4;
                                if(c < cnt) cnt = c;
                            }
                        }
                    }
                }
            }
            System.out.println(cnt == Integer.MAX_VALUE ? -1 : cnt);
        }
        br.close();
    }
    
    // 逆时针转一次
    private static void rotateCounterClockwise(int[] point){
        int x = point[0];
        point[0] = point[2] + point[3] - point[1];
        point[1] = x - point[2] + point[3];
    }
    
    private static boolean isSquare(int[][] points){
        long min = Long.MAX_VALUE, max = Long.MIN_VALUE;
        int cnt1 = 0, cnt2 = 0;
        long tmp = 0;
        for(int i = 0; i < 3; i++){
            for(int j = i+1; j < 4; j++){
                tmp = distance(points,i,j);
                if(tmp < min){min = tmp; cnt1 = 1;}
                else if(tmp == min) {cnt1++;}
                if(tmp > max){max = tmp; cnt2 = 1;}
                else if(tmp == max) {cnt2++;}
            }
        }
        return cnt1 == 4 && min != 0 && cnt2 == 2;
    }
    
    private static long distance(int[][] points, int i, int j){
        return ((long)(points[i][0] - points[j][0]))*(points[i][0] - points[j][0])
                    + (points[i][1] - points[j][1])*(points[i][1] - points[j][1]);
    }
    
}

发表于 2019-08-06 17:32:30 回复(0)
 
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[][] nums = new int[4][4];
        for (int i = 0; i < n; i++){
            for (int j = 0; j < 4; j++){
                for (int k = 0; k < 4; k++){
                    nums[j][k] = sc.nextInt();
                }
            }
            int result = findMinMoveTimes(nums);
            if (result == Integer.MAX_VALUE)
                result = -1;
            System.out.println(result);
        }
    }

    private static int findMinMoveTimes(int[][] nums) {
        int i = 0;
        int j = 0;
        int k = 0;
        int z = 0;
        int minTimes = Integer.MAX_VALUE;
        boolean flag = false;
        for (i = 0; i < 4; i++){
            if (flag){
                rotate(nums, 0);
            }
            for (j = 0; j < 4; j++){
                if (flag){
                    rotate(nums, 1);
                }
                for (k = 0; k < 4; k++){
                    if (flag){
                        rotate(nums, 2);
                    }
                    for (z = 0; z < 4; z++){
                        if (flag){
                            rotate(nums, 3);
                        }else {
                            flag = true;
                        }
                        if (isSquare(nums[0], nums[1], nums[2], nums[3])){
                            int times = i + j + k + z;
                            if (times < minTimes){
                                minTimes = times;
                            }
                        }
                    }

                }
            }
        }
        return minTimes;
    }

    private static void rotate(int[][] nums, int index) {
        int[] num = nums[index];
        int oldx = num[0];
        int oldy = num[1];
        int centerx = num[2];
        int centery = num[3];
        nums[index][0] = centerx + centery - oldy;
        nums[index][1] = centery - centerx + oldx;
    }

    private static boolean isSquare(int[] neePoint1, int[] neePoint2, int[] neePoint3, int[] neePoint4){
        long[] dis = new long[6];
        dis[0] = dis(neePoint1, neePoint2);
        dis[1] = dis(neePoint1, neePoint3);
        dis[2] = dis(neePoint1, neePoint4);
        dis[3] = dis(neePoint2, neePoint3);
        dis[4] = dis(neePoint2, neePoint4);
        dis[5] = dis(neePoint3, neePoint4);
        int count = 0;
        long minDis = Long.MAX_VALUE;
        for (int i = 0; i < 6; i++){
            if (dis[i] < minDis){
                minDis = dis[i];
            }
        }
        for (int i = 0; i < 6; i++){
            if (dis[i] == minDis){
                count++;
            }
        }
        return count == 4;
    }

    private static long dis(int[] neePoint1, int[] neePoint2) {
        long x = neePoint1[0] - neePoint2[0];
        long y = neePoint1[1] - neePoint2[1];
        return (x * x + y * y);
    }


}


发表于 2018-09-04 23:42:38 回复(1)
#include <bits/stdc++.h>
using namespace std;
int cnt;
class P{
public:
    int x,y;
    P(){};
    P(int x, int y):x(x),y(y){};
    void R(P c){
        int dx = x - c.x;
        int dy = y - c.y;
        x = c.x - dy;
        y = c.y + dx;
        return;
    }
};

double Dist(P p1, P p2){
    return sqrt(pow(p1.x-p2.x,2) + pow(p1.y-p2.y,2));
}

bool F(vector<P> p){
    double d[6];
    for(int i=0,k=0;i<4;i++)
        for(int j=i+1;j<4;j++)
            d[k++] = Dist(p[i], p[j]);
    sort(d, d+6);
    if(d[0]!=0 && d[0]==d[1] && d[0]==d[2] && d[0]==d[3] && d[4]==d[5])
        return true;
    return false;
}

void DFS(P *p, P *c, vector<P> &r, int k, int s){
    if(r.size()==4){
        if(F(r))
            cnt = min(cnt, s);
        return;
    }
    int t=0;
    P q = p[k];
    for(int i=0;i<4;i++){
        r.push_back(q);
        DFS(p, c, r, k+1, s+t);
        r.pop_back();
        q.R(c[k]);
        t++;
    }
    return ;
}

int main(){
    int n;
    cin>>n;
    int a,b,x,y;
    P p[4],c[4];
    for(int i=0;i<n;i++){
        for(int j=0;j<4;j++){
            cin>>a>>b>>x>>y;
            p[j] = P(a, b);
            c[j] = P(x, y);
        }
        cnt = INT_MAX;
        vector<P> r;
        DFS(p, c, r, 0, 0);
        cout<<((cnt==INT_MAX)?-1:cnt)<<endl;
    }
    return 0;
}

发表于 2019-12-02 01:33:50 回复(0)


## 笛卡尔坐标系内点旋转公式:
(a,b)为旋转中心,(x,y)为旋转初始点,(x',y')为旋转目标点

θ 是逆时针的旋转角
x' = xcosθ  - ysinθ  + a(1-cosθ ) + bsinθ 
y' = xsinθ  + ycosθ  + a(-sinθ ) + b(1-cosθ) 

当θ = 90°时
x' =  -y + a + b
y' = x -a + b

对每一组点,能构成的排列组合形式有 4* 4* 4* 4共256种可能性,可以直接枚举。
## 如何判断四个点能否构成正方形
    判断方法如下:
    若有3个点的x相等或3个点的y相等,直接为false
    选定1个点p1, 则其余3个点分别为:p2,p3,p4
    始终以p1作为要判断的角的顶点,则有如下几种可能:
        p1与p2对角,p1p3 = p1p4=p2p3=p2p4,且p3p1p4为直角
        p1与p3对角,p1p2 = p1p4=p3p2=p3p4,且p2p1p4为直角
        p1与p4对角,p1p2 = p1p3=p4p2=p4p3,且p2p1p3为直角

1.距离:
两个点(x,y), (x',y')之间的距离为sqrt((x-x')^2+(y-y')^2)
仅做相等判断的话,则可不用根号,直接用根号内的公司判断即可

2.角度
判断三点连续构成的角是否为直角,第一个点参数为顶点:
bool IsRightAngle(int x1,int y1,int x2,int y2,int x3,int y3){
    if((x2-x1)* (x3-x1)+(y2-y1)* (y3-y1)==0)
        return true;
    return false;
}

import java.util.Scanner;

public class Main {
    static class Point{
        int x;
        int y;

        Point(int x, int y){
            this.x = x;
            this.y = y;
        }
        //返回该点与点p之间距离的的平方
        int squareOfDistance(Point p){
            return (p.x-x)*(p.x-x) + (p.y-y)*(p.y-y);
        }
    }

    static class PointGroup{
        Point pivot; //轴点
        Point main;  //主点

        PointGroup(Point m, Point p){
            main = m;
            pivot = p;
        }

    }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();

        //每4个点是一组
        PointGroup[][] points = new PointGroup[n][4];
        for(int i=0;i<n;i++){
            for(int j=0;j<4;j++){
                Point m = new Point(in.nextInt(), in.nextInt());
                Point p = new Point(in.nextInt(),in.nextInt());
                points[i][j] = new PointGroup(m, p);
            }
        }

        int[] ans = new int[n];
        for(int i=0;i<n;i++){
            Point p1,p2,p3,p4;

            int minStep = Integer.MAX_VALUE;
            for(int i1=0;i1<4;i1++){
                p1 = rotate(points[i][0].main, points[i][0].pivot, i1);
                for(int i2=0;i2<4;i2++){
                    p2 = rotate(points[i][1].main, points[i][1].pivot, i2);
                    for(int i3=0;i3<4;i3++){
                        p3 = rotate(points[i][2].main, points[i][2].pivot, i3);
                        for(int i4=0;i4<4;i4++){
                            p4 = rotate(points[i][3].main, points[i][3].pivot, i4);
                            if(isSquare(p1,p2,p3,p4)){
                                minStep = Math.min(minStep, i1+i2+i3+i4);
                            }
                         }
                    }
                }
            }
            if(minStep==Integer.MAX_VALUE) ans[i]=-1;
            else ans[i]=minStep;
        }

        for(int i=0;i<n;i++){
            System.out.println(ans[i]);
        }

    }

    //将p绕pivot旋转count个90度后的点返回
    public static Point rotate(Point p, Point pivot, int count){
        Point ans = new Point(p.x, p.y);
        Point pre = new Point(p.x, p.y);
        for(int i=0;i<count;i++){
            ans.x = -pre.y+pivot.x+pivot.y;
            ans.y = pre.x - pivot.x + pivot.y;
            pre.x = ans.x;
            pre.y = ans.y;
        }
        return ans;
    }

    public static boolean isRightAngle(Point p1, Point p2, Point p3){
        if((p2.x-p1.x)* (p3.x-p1.x)+(p2.y-p1.y)* (p3.y-p1.y)==0)
            return true;
        return false;
    }

    //判断四个点能否构成正方形
    public static boolean isSquare(Point p1, Point p2, Point p3, Point p4){
        //若有三个点x或y相等,直接返回false
        if((p1.x==p2.x && p1.x==p3.x) || (p1.x==p2.x && p1.x==p4.x) || (p1.x==p3.x && p4.x==p3.x)|| (p2.x==p3.x && p4.x==p3.x)
            || (p1.y==p2.y && p1.y==p3.y) || (p1.y==p2.y && p1.y==p4.y) || (p1.y==p3.y && p4.y==p3.y)|| (p2.y==p3.y && p4.y==p3.y)){
            return false;
        }
        //若始终以p1作为要判断的角的顶点,则有如下几种可能:
        /*
        p1与p2对角,p1p3 = p1p4=p2p3=p2p4,且p3p1p4为直角
        p1与p3对角,p1p2 = p1p4=p3p2=p3p4,且p2p1p4为直角
        p1与p4对角,p1p2 = p1p3=p4p2=p4p3,且p2p1p3为直角
         */
        if(p1.squareOfDistance(p3)==p1.squareOfDistance(p4) && p2.squareOfDistance(p3)==p2.squareOfDistance(p4) && p1.squareOfDistance(p4) == p2.squareOfDistance(p3)){
            if(isRightAngle(p1,p3,p4)) return true;
            else return false;
        }

        if(p1.squareOfDistance(p2)==p1.squareOfDistance(p4) && p3.squareOfDistance(p2)==p3.squareOfDistance(p4) && p1.squareOfDistance(p2) == p3.squareOfDistance(p2)){
            if(isRightAngle(p1,p2,p4)) return true;
            else return false;
        }

        if(p1.squareOfDistance(p2)==p1.squareOfDistance(p3) && p4.squareOfDistance(p2)==p4.squareOfDistance(p3) && p1.squareOfDistance(p2) == p4.squareOfDistance(p3)){
            if(isRightAngle(p1,p2,p3)) return true;
            else return false;
        }
        return false;
    }
}


发表于 2019-10-25 16:22:01 回复(0)
#include <bits/stdc++.h>
#define sc scanf
#define pr printf
#define ll long long
using namespace std;
const int MAXN = 1e5 + 5;
const double PI = acos(-1.0);
const double eps = 1e-6;
struct point
{
    int x;
    int y;
}t[4], temp[4];
struct node
{
    point cur;//原点
    point xuan;//旋转的点
    void scan() { sc("%d%d%d%d", &cur.x, &cur.y, &xuan.x, &xuan.y); }
}in[4];
bool check()
{
    for (int i = 0; i < 4; i++)
        temp[i] = t[i];
    sort(temp, temp + 4, [](point q, point w) {
        if (q.x == w.x)
            return q.y < w.y;
        else
            return q.x < w.x;
        });
    if (temp[0].x == temp[3].x && temp[0].y == temp[3].y)
        return false;
    if (temp[0].y == temp[2].y && temp[1].y == temp[3].y && temp[0].x == temp[1].x && temp[2].x == temp[3].x && temp[3].y - temp[2].y == temp[3].x - temp[1].x && temp[3].x - temp[1].x == temp[1].y - temp[0].y && temp[1].y - temp[0].y == temp[2].x - temp[0].x)
        return true;
    return false;
}
point rotate(point a, point o, int angle)//逆时针 angle = angle * 90
{
    point t = point{ a.x - o.x,a.y - o.y };
    //int c = cos(angle), s = sin(angle);
    int c, s;
    if (angle == 0)
        c = 1, s = 0;
    else if (angle == 1)
        c = 0, s = 1;
    else if (angle == 2)
        c = -1, s = 0;
    else
        c = 0, s = -1;
    return point{ o.x + t.x * c - t.y * s,o.y + t.x * s + t.y * c };
}
int main()
{
    int T;
    sc("%d", &T);
    while (T--)
    {
        for (int i = 0; i < 4; i++)
            in[i].scan();
        int ans = 100000;
        for (int i = 0; i < 4; i++)
        {
            t[0] = rotate(in[0].cur, in[0].xuan, i);
            for (int j = 0; j < 4; j++)
            {
                t[1] = rotate(in[1].cur, in[1].xuan, j);
                for (int k = 0; k < 4; k++)
                {
                    t[2] = rotate(in[2].cur, in[2].xuan, k);
                    for (int l = 0; l < 4; l++)
                    {
                        t[3] = rotate(in[3].cur, in[3].xuan, l);
                        if (check())
                            ans = min(ans, i + j + k + l);
                    }
                }
            }
        }
        if (ans == 100000)
            ans = -1;
        pr("%d\n", ans);
    }
}
枚举4个杂物需要逆时针旋转几次,然后将angle换成次数,预处理次数到角度,防止浮点误差
判断是否合法的时候,只需要将4个点二维偏序排序,若答案合法的话,正方形的四个点的位置在排序后是确定的。所以可以直接判断
发表于 2019-09-11 09:26:47 回复(0)
"""
列出逆时针旋转所有可能的坐标点,
枚举4*4*4*4种可能组合,找到最小可组成方形的旋转次数
"""
import sys


def rot90(a, b, x, y):
    return [y - b + x, a - x + y]


def dis(point1, point2):
    return (point1[0] - point2[0]) ** 2 + (point1[1] - point2[1]) ** 2


def is_square(clutter, i, j, k, t):
    point1, point2, point3, point4 = clutter[0][i], clutter[1][j], clutter[2][k], clutter[3][t]
    q = [dis(point1, point2), dis(point1, point3), dis(point1, point4), dis(point2, point3), dis(point2, point4),
         dis(point3, point4)]
    q.sort()
    if q[0] > 0 and q[0] == q[1] == q[2] == q[3] == q[4] / 2 == q[5] / 2:
        return True
    return False


if __name__ == "__main__":
    # sys.stdin = open('input.txt', 'r')
    n = int(input().strip())
    for _ in range(n):
        clutter = []
        for _ in range(4):
            a, b, x, y = list(map(int, input().strip().split()))
            tmp = [[a, b]]
            for _ in range(3):
                tmp.append(rot90(tmp[-1][0], tmp[-1][1], x, y))
            clutter.append(tmp)
        ans = 100
        for i in range(4):
            for j in range(4):
                for k in range(4):
                    for t in range(4):
                        if is_square(clutter, i, j, k, t):
                            ans = min(ans, i + j + k + t)
        if ans > 3 * 4:
            ans = -1
        print(ans)

发表于 2019-07-03 17:06:50 回复(0)
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main() {
    int n;
    cin >> n;
    for (int i = 0; i != n; ++i) {
        vector<vector<pair<int, int>>>edge(4, vector<pair<int, int>>(4, { 0,0 }));
        for (int j = 0; j != 4; ++j) {
            int a, b, x, y;
            cin >> a >> b >> x >> y;
            edge[j][0] = { a,b };
            for (int k = 1; k != 4; ++k)
                edge[j][k] = { x + y - edge[j][k - 1].second,y - x + edge[j][k - 1].first };
        }
        int mincost = 0x7FFFFFFF;
        for (int a = 0; a != 4; ++a)
            for (int b = 0; b != 4; ++b) 
                for (int c = 0; c != 4; ++c) 
                    for (int d = 0; d != 4; ++d) {
                        vector<pair<int, int>>temp{ edge[0][a],edge[1][b],edge[2][c],edge[3][d] };
                        sort(temp.begin(), temp.end());
                        if (temp[1].second - temp[0].second != 0&&
                            temp[1].second - temp[0].second == temp[2].first - temp[0].first&&
                            temp[3].second - temp[2].second == temp[2].first-temp[0].first&&
                            temp[3].second - temp[1].second == temp[1].first-temp[0].first)
                            mincost = min(mincost, a + b + c + d);
                    }
        cout << (mincost == 0x7FFFFFFF ? -1 : mincost) << endl;
    }
    return 0;
}
一开始想当然把正方形当正立的了,但是居然过了。。,多谢牛油的指正。
编辑于 2018-08-16 10:44:28 回复(0)
写了好久的蛋疼玩意儿
#include<bits/stdc++.h>
using namespace std;
int da[4][4];//记录每次四个物品位置坐标和旋转坐标
long long dis(int a,int b,int c,int d){//两点距离的平方
    return (long long )((a-c)*(a-c))+(long long)((b-d)*(b-d));
}
bool isSquare(){//判断是否是正方形
    long long a[6],t=0;
    for(int i=0;i<4;i++){
        for(int j=i+1;j<4;j++){
            a[t++]=dis(da[i][0],da[i][1],da[j][0],da[j][1]);
        }
    }
    sort(a,a+6);
    return a[0]!=0&&a[0]==a[3]&&a[0]*2==a[4]&&a[4]==a[5];
}

void rotate(int index){//逆时针旋转1次
    int a=da[index][0],b=da[index][1],x=da[index][2],y=da[index][3];
    da[index][0]=x+y-b;
    da[index][1]=-x+y+a;
}
void rotate(int index,int cnt){//逆时针旋转cnt次
    while(cnt--){
        rotate(index);
    }
}
int getNum(){
    int res=INT_MAX;
    //暴力检索,i,j,k,l分别表示物品1,2,3,4的旋转次数
    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++){
                    //逆时针旋转
                    rotate(0,i);
                    rotate(1,j);
                    rotate(2,k);
                    rotate(3,l);
                    if(isSquare()){//是正方形就记录次数
                        res=min(res,i+j+k+l);
                    }
                    //本次旋转结束,把物品旋转回去,即再逆时针旋转4-x次
                    rotate(0,4-i);
                    rotate(1,4-j);
                    rotate(2,4-k);
                    rotate(3,4-l);
                }
            }
        }
    }
    return res==INT_MAX?-1:res;//没找到返回-1,找到返回res
}

int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        for(int j=0;j<4;j++){
            scanf("%d%d%d%d",&da[j][0],&da[j][1],&da[j][2],&da[j][3]);
        }
        printf("%d\n",getNum());
    }
}


发表于 2019-12-05 15:31:51 回复(0)
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text.RegularExpressions;

namespace Test0001
{   
    public struct Vector2
    {
        public long x;
        public long y;
        public Vector2(long x, long y)
        {
            this.x = x;
            this.y = y;
        }
    }
    class Program
    {
        public static void Main(string[] args)
        {
            string line;
            while (!string.IsNullOrEmpty(line = Console.ReadLine())) Func(line);
        }
        //A(ai,bi) 围绕 O(xi,yi) 逆时针旋转
        // x = ai - xi   y = bi - yi
        //90°  A1(xi-y,yi+x)
        //180° A2(xi-x,yi-y)
        //270° A3(xi+y,yi-x)

        //正方形性质 四条边长一样 且对角线相等 并且长度大于0


        public static void Func(string line)
        {
            int n = int.Parse(line);
            for (int i = 0; i < n; i++)
            {
                //四个坐标
                var A1 = RotationVector2(Console.ReadLine());
                var A2 = RotationVector2(Console.ReadLine());
                var A3 = RotationVector2(Console.ReadLine());
                var A4 = RotationVector2(Console.ReadLine());
                int a1 = 0, a2 = 0, a3 = 0, a4 = 0;
                int min = int.MaxValue;
                while (true) //4 * 4 * 4 * 4 =256种情况
                {
                    if(IsSquare(A1[a1], A2[a2], A3[a3], A4[a4]))
                    {
                        min = Math.Min(a1 + a2 + a3 + a4, min);
                    }
                    a4++;
                    if (a4 > 3)
                    {
                        a4 = 0;
                        a3++;
                        if (a3 > 3)
                        {
                            a3 = 0;
                            a2++;
                            if (a2 > 3)
                            {
                                a2 = 0;
                                a1++;
                                if (a1 > 3)
                                {
                                    break;
                                }
                            }
                        }
                    }
                }
                Console.WriteLine(min == int.MaxValue ? -1 : min);
            }
        }

        public static Vector2[] RotationVector2(string str)
        {
            var arr = str.Trim().Split().Select(m => long.Parse(m)).ToArray();
            long ai = arr[0], bi = arr[1], xi = arr[2], yi = arr[3];
            long x = ai - xi ,  y = bi - yi;
            Vector2[] vector2s = new Vector2[4]
            {
                new Vector2(ai,bi),
                new Vector2(xi-y,yi+x),
                new Vector2(xi-x,yi-y),
                new Vector2(xi+y,yi-x)
            };
            return vector2s;
        }
        /// <summary>
        /// 四个点是否构成正方形
        /// </summary>
        /// <returns></returns>
        public static bool IsSquare(Vector2 v1, Vector2 v2, Vector2 v3, Vector2 v4)
        {
            if (v1.Equals(v2) && v2.Equals(v3) && v3.Equals(v4)) return false; 
            //四个点不能是同一个点
            long[] res = new long[6];
            res[0] = (v1.x - v2.x) * (v1.x - v2.x) + (v1.y - v2.y) * (v1.y - v2.y);
            res[1] = (v2.x - v3.x) * (v2.x - v3.x) + (v2.y - v3.y) * (v2.y - v3.y);
            res[2] = (v3.x - v4.x) * (v3.x - v4.x) + (v3.y - v4.y) * (v3.y - v4.y);
            res[3] = (v4.x - v1.x) * (v4.x - v1.x) + (v4.y - v1.y) * (v4.y - v1.y);
            res[4] = (v1.x - v3.x) * (v1.x - v3.x) + (v1.y - v3.y) * (v1.y - v3.y);
            res[5] = (v2.x - v4.x) * (v2.x - v4.x) + (v2.y - v4.y) * (v2.y - v4.y);
            res = res.OrderBy(x => x).ToArray();
            //其次 四条边相等并且对角线相等 对角线大于边
            return res[0] == res[1] && res[1] == res[2] && res[2] == res[3] && res[3] < res[4] && res[4] == res[5];
        }
    }
}

用的很笨很简单的方法,本题没有什么复杂的逻辑,枚举出所有可能一次判断之后选取最小旋转次数即可
首先对于点坐标的旋转
A(ai,bi) 围绕 O(xi,yi) 逆时针旋转
x = ai - xi   y = bi - yi
90°  A1(xi-y,yi+x)
180° A2(xi-x,yi-y)
270° A3(xi+y,yi-x)
根据公式可以直接得到改点旋转可能得到的4个坐标 然后将四个坐标存到一个长度为4的数组A中
由此可以得到A[0] 旋转0次的坐标 A[1] 旋转1次的坐标,以此类推
之后枚举所有情况 从 0 0 0 0 -> 0 0 0 1 -> ...... -> 3 3 3 3 为止 所有情况依次判断
关于如何判断是否为正方形,我也用了一个比较笨的方法  首先四个点不得是同一个点
其次计算出6条边利用勾股定理 (x0-x1)^2 + (x0 - y1)^2 如果开根号就是长度,不过在此题中没必要 平方相等长度一定相等(长度>0)  为什么一定要六条 ,我不清楚 正方形是abcd 还是abdc这样连接,由此我不能判断他是否是边还是对角线 ,因此 用了一个数组存放6条边然后进行排序 对角线一定比边长,所以最后两个必然是对角线.


发表于 2019-12-03 11:46:28 回复(0)
//暴力枚举,判断正方形时,以某一点为起点求出三个向量,
//如果其中两个向量正交,且第三个向量等于它们的和,
//则三个向量的终点和该起点能构成正方形
#include<bits/stdc++.h>

using namespace std;

void rotate(int &a, int &b, int x, int y){
    int tmpb = y - (x - a);
    int tmpa = x - (b - y);
    a = tmpa, b = tmpb;
}

bool check(int a[], int b[]){
    int i=a[1]-a[0],j=b[1]-b[0];
    int k=a[2]-a[0],l=b[2]-b[0];
    int m=a[3]-a[0],n=b[3]-b[0];
    if((i*m+j*n==0&&i*i+j*j==m*m+n*n&&m+i==k&&n+j==l)||
      (k*m+l*n==0&&k*k+l*l==m*m+n*n&&m+k==i&&n+l==j)||
      (i*k+j*l==0&&i*i+j*j==k*k+l*l&&k+i==m&&l+j==n))
        return true;
    return false;
}
int getMin(int a[], int b[], int x[], int y[]){
    int res = 0;
    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++){
                    if(check(a, b)){
                        return i+j+k+l; 
                    }
                    rotate(a[3], b[3], x[3], y[3]);
                }
                rotate(a[2], b[2], x[2], y[2]);
            }
            rotate(a[1], b[1], x[1], y[1]);
        }
        rotate(a[0], b[0], x[0], y[0]);
    }
    return -1;
}
int main(){
    int n;
    cin>>n;
    while(n--){
        int a[4],b[4],x[4],y[4];
        for(int i = 0; i < 4; i++){
            cin>>a[i]>>b[i]>>x[i]>>y[i];
        }
        cout << getMin(a,b,x,y) << endl;
    }
}

发表于 2019-11-12 10:27:26 回复(0)
import sys def point(sourse,t): p=[] if t == 0:
        p = [sourse[0], sourse[1]] elif t == 1:
        p = [sourse[2] + sourse[3] - sourse[1],  -sourse[2] + sourse[3] + sourse[0]] elif t == 2:
        p = [2 * sourse[2] - sourse[0], 2 * sourse[3] - sourse[1]] else:
        p = [sourse[2] - sourse[3] + sourse[1],  sourse[2] + sourse[3] - sourse[0]] return p def isSqu(p1,p2,p3,p4):
    d1=  (p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2  d2 = (p1[0] - p3[0]) ** 2 + (p1[1] - p3[1]) ** 2  d3 = (p1[0] - p4[0]) ** 2 + (p1[1] - p4[1]) ** 2  d4 = (p2[0] - p3[0]) ** 2 + (p2[1] - p3[1]) ** 2  d5 = (p2[0] - p4[0]) ** 2 + (p2[1] - p4[1]) ** 2  d6 = (p3[0] - p4[0]) ** 2 + (p3[1] - p4[1]) ** 2  dic={}
    arr=[d1,d2,d3,d4,d5,d6] for item in arr: if item in dic.keys():
            dic[item]=dic[item]+1  else:
            dic[item]=1  if len(dic)==2 and (dic[d1]==2 or dic[d1]==4) and not dic.__contains__(0): return 1  else: return 0  n=int(input())
sourse=[] for i in range(4*n):
    str=sys.stdin.readline()
    sourse.append([int(str.split()[0]),int(str.split()[1]),int(str.split()[2]),int(str.split()[3])]) for i in range(n):
    temp=16  flag=0  for t1 in range(4):
        p1=point(sourse[4*i],t1) for t2 in range(4):
            p2=point((sourse[4*i+1]),t2) for t3 in range(4):
                p3=point(sourse[4*i+2],t3) for t4 in range(4):
                    p4=point(sourse[4*i+3],t4) if isSqu(p1,p2,p3,p4):
                        flag=1  temp = min(t1 + t2 + t3 + t4, temp) #print(p1,p2,p3,p4,t1+t2+t3+t4)   if flag==0:
        temp=-1    print(temp)
发表于 2019-11-04 23:47:54 回复(0)
// 穷举法
// 对点的所有移动方法进行遍历,判断每个点能否构成正方形

function rotate(a, b, x, y){
    return [x+y-b, y+a-x]
}

function dis(a1,b1, a2,b2){
    return (a2 - a1) ** 2 + (b2 - b1) ** 2
}
function isSquare(...points){ // [[x,y], [x, y]]
    
    let edges = []
    for(let i = 0; i < 3; i++){
        for(let j = i+1; j < 4; j++){
            edges.push(dis(...points[i], ...points[j]))
        }
    }
    edges.sort((x,y)=>x-y)
    if (edges[0] != 0 && // 面积不为0
        edges.slice(0, 4).every(d=>d===edges[0]) && // 前四个边相同
        edges.slice(4).every(d=>d===edges[4]) &&  // 后两个对角线相同
        edges[4] == 2 * edges[0]){ // 对角线的平方是边长的两倍
        
        return true
    }  
    
    return false
}
function solve(arrMap){
    let counter = 0
    let min = 100
    
    let temp = arrMap.map(d=>{
        let [a,b,x,y] = d
        let allRotate = [[a,b]]
        
        for(let i = 0; i < 3; i++){
            allRotate.push(rotate(...allRotate[allRotate.length - 1], x, y))
        }
        return allRotate
    })

    for(let i = 0; i < 4; i++){
        for(let j = 0; j < 4; j++){
            for(let m = 0; m < 4; m++){
                for(let n = 0; n < 4; n++){
                    if(isSquare(temp[0][i], temp[1][j], temp[2][m], temp[3][n])){
                        min = Math.min(min, i+j+m+n)
                    }
                }
            }
        }
    }
    
    return min === 100 ? -1 : min
}

let n = +readline()
let inputs = []
for(let i = 0; i < n; i++){
    let temp = []
    for(let i = 0; i< 4; i++){
        temp.push(readline().split(' ').map(d=>+d))
    }
    
    inputs.push(temp)
}
    
 for(let i = 0; i < n; i++){
    let result = solve(inputs[i])
    console.log(result)
}

发表于 2019-08-22 12:55:45 回复(0)
import java.util.*;

class Point{
    int x;
    int y;
    Point(int x,int y){
        this.x = x;
        this.y = y;
    }
}

public class Main{
    
    //逆时针旋转90度坐标
    //A --要变换的点 P --旋转中心
    public static void roate90(Point A,Point p){
        int x = A.x - p.x;
        int y = A.y - p.y;
        int tmp = x;
        x = -y+p.x;
        y = tmp+p.y;
        A.x = x;
        A.y = y;
    }
    //旋转count次后点的坐标
    public static Point roateCount(Point p,Point center,int count){
        Point A = new Point(p.x,p.y);
        if(count==0) return A;
        for(int i=0;i<count;i++)
        	roate90(A,center);
        return A;
    }
    
    //两点距离
    public static int dist2(Point A,Point B){
        return (int)(Math.pow(A.x-B.x,2)+Math.pow(A.y-B.y,2));
    }
    
    public static boolean isRect(Point A,Point B,Point C,Point D){
        Point[] ps = new Point[4];
        int x =0,y=0;
        ps[0] = A;
        ps[1] = B;
        ps[2] = C;
        ps[3] = D;
        //set用于判断是不是正方形(正方形两顶点的值只有两种)
        HashSet<Integer> set = new HashSet<Integer>();
        for(int i=0;i<3;i++){
            for(int j=i+1;j<4;j++){
                int d =dist2(ps[i],ps[j]);
                if(d==0) return false;//两点重合,不构成正方形
                set.add(d);
            }
        }
        if(set.size()==2) return true;
        else return false;
    }
    
    public static void main(String[] args){
        Scanner sca = new Scanner(System.in);
        int n = sca.nextInt();
        Point[] obj = new Point[4];
        Point[] center = new Point[4];
        while(n>0){
            for(int i=0;i<4;i++){
                int x = sca.nextInt();
                int y = sca.nextInt();
                obj[i] = new Point(x,y);
                x = sca.nextInt();
                y = sca.nextInt();
                center[i] = new Point(x,y);
            }
            int res = Integer.MAX_VALUE;
            for(int a=0;a<4;a++){
                Point A = roateCount(obj[0],center[0],a);
                for(int b=0;b<4;b++){
                    Point B = roateCount(obj[1],center[1],b);
                    for(int c=0;c<4;c++){
                        Point C = roateCount(obj[2],center[2],c);
                        for(int d=0;d<4;d++){
                            Point D = roateCount(obj[3],center[3],d);
                            if(isRect(A,B,C,D)) res=Math.min(res,a+b+c+d);
                        }
                    }
                }
            }
            if(res==Integer.MAX_VALUE) res = -1;
            System.out.println(res);
            n--;
        }
    }
}

发表于 2019-08-21 17:10:22 回复(0)
#include<iostream>
#include<vector>
#include<utility>
#include<math.h>

using namespace std;
//将点(a,b)绕着(x,y)逆时针旋转90°进行k次
pair<int,int> rotate(int a,int b,int x,int y,int k){
    for(int i=0;i<k;i++){
        int tmp=a;    //注意a随时改变,需要提前暂存
        a=y-b+x;
        b=tmp-x+y;
    }
    pair<int,int> p;
    p.first=a;p.second=b;
    return p;
}
//判断四个点是否是正方形
bool isSq(pair<int,int> p1,pair<int,int> p2,pair<int,int> p3,pair<int,int> p4){
    //四个点的横坐标是否是两两相等
    bool rx = ((p1.first) ^ (p2.first) ^ (p3.first) ^ (p4.first)) == 0;
    //四个点的横坐标是否是两两相等
    bool ry = ((p1.second) ^ (p2.second) ^ (p3.second) ^ (p4.second)) == 0;
    //是否是矩形,横纵坐标至少1个不两两相等或者某一个坐标的值全相等
    if (rx==false || ry==false || rx && ry && (p1.first == p2.first && p1.first == p3.first) ||
        rx && ry && (p1.second == p2.second && p1.second == p3.second)) 
        return false;
    //判断正方形,边长相等
    int dx = abs((p1.first - p2.first) != 0 ? (p1.first - p2.first) : (p1.first - p3.first));
    int dy = abs((p1.second - p2.second) != 0 ? (p1.second - p2.second) : (p1.second - p3.second));
    return dx == dy;
}

//如果旋转不成正方形,则输出-1
int minStep(vector<vector<int>>& vec){
    pair<int,int> p1,p2,p3,p4;
    int res=-1,tmp=1000000;
    for(int k1=0;k1<=3;k1++){
        p1=rotate(vec[0][0],vec[0][1],vec[0][2],vec[0][3],k1);
        for(int k2=0;k2<=3;k2++){
            p2=rotate(vec[1][0],vec[1][1],vec[1][2],vec[1][3],k2);
            for(int k3=0;k3<=3;k3++){
                p3=rotate(vec[2][0],vec[2][1],vec[2][2],vec[2][3],k3);
                for(int k4=0;k4<=3;k4++){
                    p4=rotate(vec[3][0],vec[3][1],vec[3][2],vec[3][3],k4);
                    //判断4个点是否能构成正方形
                    if(isSq(p1,p2,p3,p4)&&(k1+k2+k3+k4<tmp))
                        tmp=k1+k2+k3+k4;
                }
            }
        }
    }
    if(tmp<1000000)
        res=tmp;
    return res;
}

void solver(){
    int n;    //杂物的团数
    cin>>n;
    vector<int> res;
    for(int i=0;i<n;i++){
        vector<vector<int>> vec;
        for(int j=0;j<4;j++){
            vector<int> tmp(4,0);
            cin>>tmp[0]>>tmp[1]>>tmp[2]>>tmp[3];
            vec.push_back(tmp);
        }
        //计算该杂物最少移动的步数
        int step=minStep(vec);
        res.push_back(step);
    }
    for(int i=0;i<res.size();i++)
        cout<<res[i]<<endl;
}

int main(){
    solver();
    return 0;
}

发表于 2019-08-15 22:04:26 回复(0)
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
//求俩点距离的平方,int会超
long long GetDis(paira, pairb)
{
    return pow(a.first - b.first, 2) + pow(a.second - b.second, 2);
}
int main() {
    int n; cin >> n;
    //存储所有数据 如a[0][1].{{1,2}代表输入的第一个数旋转一次后的坐标为(1,2)
    vector<vector<pair<int, int>> > a(4,vector<pair<int,int>>(4));  

   pair<int, int> tmp;
    for (int i = 0; i < n; i++)
    {
        //输入数据并处理
        for (int j = 0; j < 4; j++)
        {
            cin >> a[j][0].first >> a[j][0].second;
            cin >> tmp.first >> tmp.second;
            for (int k = 0; k < 3; k++)
            {
                a[j][k + 1].first = tmp.first - a[j][k].second + tmp.second;
                a[j][k + 1].second = tmp.second - tmp.first + a[j][k].first;
            }
        }
        //判断是否为正方形,4个点 组成6条边,4条短的相同,2条长的相同,
        //注意一定要比较长短,不然可能出现面积为0的正方形
        int minn = 16;//最大次数不可能超过12
        for(int fa=0;fa<4;fa++)
            for (int fb = 0; fb < 4; fb++)
                for (int fc = 0; fc < 4; fc++)
                    for (int fd = 0; fd < 4; fd++)
                    {
                        vector<long long> x;
                        x.push_back(GetDis(a[0][fa], a[1][fb]));
                        x.push_back(GetDis(a[0][fa], a[2][fc]));
                        x.push_back(GetDis(a[0][fa], a[3][fd]));
                        x.push_back(GetDis(a[1][fb], a[2][fc]));
                        x.push_back(GetDis(a[1][fb], a[3][fd]));
                        x.push_back(GetDis(a[2][fc], a[3][fd]));
                        sort(x.begin(), x.end());
                        if (x[0] == x[3] && x[4] == x[5]&&x[4]>x[3])
                        {
                            minn = min(minn, fa + fb + fc + fd);
                        }
                    }
        cout << (minn == 16 ? -1 : minn )<< endl;
    }
    system("pause");
}

编辑于 2019-08-15 19:11:13 回复(0)