又到了周末，小易的房间乱得一团糟。
他希望将地上的杂物稍微整理下，使每团杂物看起来都紧凑一些，没有那么乱。
地上一共有n团杂物，每团杂物都包含4个物品。第i物品的坐标用(ai,bi)表示，小易每次都可以将它绕着(xi,yi)逆时针旋转
，这将消耗他的一次移动次数。如果一团杂物的4个点构成了一个面积不为0的正方形，我们说它是紧凑的。
因为小易很懒，所以他希望你帮助他计算一下每团杂物最少需要多少步移动能使它变得紧凑。
[编程题]整理房间
- 热度指数：5627 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
- 算法知识视频讲解
输入描述:
第一行一个数n(1 <= n <= 100)，表示杂物的团数。
接下来4n行，每4行表示一团杂物，每行4个数ai, bi，xi, yi, (-104 <= xi, yi, ai, bi <= 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次。
这种题真的很考验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)
#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)
- 如何判断四个点能否组成正方形: 假设四个点编号为[1, 2, 3, 4], 考虑正方形的对称性, 检查i) 1->2->3->4, ii) 1->3->2->4, iii) 1->2->4->3 这三种情况能否组成正方形即可. 确定顺序后四条边边长相等且对角线长度相等即可组成正方形.
- 如何绕将点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
- 如何确定最小操作次数: 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 ¢er) {
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> ¢ers, 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)
// 穷举
// 逆时针转四次就转回去了,所以每次直接修改原数组就可以了,不用定义另外的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)
枚举所有情况判断是否形成正方形
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)
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 X[4][4],Y[4][4];//分别存放四个点逆时针旋转的横坐标和纵坐标
map<int,int>mp;//判断四个点围成的是否是正方形
bool judge(int x1,int y1,int x2,int y2,int x3,int y3,int x4,int y4){
mp.clear();
mp[(x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)]++;
mp[pow((x1-x3),2)+pow((y1-y3),2)]++;
mp[pow((x1-x4),2)+pow((y1-y4),2)]++;
mp[pow((x2-x3),2)+pow((y2-y3),2)]++;
mp[pow((x2-x4),2)+pow((y2-y4),2)]++;
mp[pow((x3-x4),2)+pow((y3-y4),2)]++;
if(mp.size()==2&&!mp.count(0))return 1;//当mp元素是两个并且没有0元素为真，因为可能会有相同坐标出现
return 0;
}
int answer(int x[4][4],int y[4][4]){
int ans = 1000000;
for(int i = 0;i<4;i++){//枚举四个点所有旋转过的坐标判断是否是正方形，更新答案
for(int j = 0;j<4;j++){
for(int m = 0;m<4;m++){
for(int n = 0;n<4;n++){
if(judge(x[0][i],y[0][i],x[1][j],y[1][j],x[2][m],y[2][m],x[3][n],y[3][n])){
ans = min(ans,i+j+m+n);
cout<<ans<<endl;
}
}
}
}
}
return ans;
}
int main(){
int n;
cin>>n;
while(n--){
for(int i = 0;i<4;i++){
int x,y,a,b;
cin>>x>>y>>a>>b;
X[i][0] = x,Y[i][0] = y;//以下四行是求每个点逆时针旋转的横纵坐标
X[i][1] = a-(y-b),Y[i][1] = b+(x-a);
X[i][2] = a-(Y[i][1]-b),Y[i][2] = b+(X[i][1]-a);
X[i][3] = a-(Y[i][2]-b),Y[i][3] = b+(X[i][2]-a);
}
int ans = answer(X,Y);
if(ans==1000000)cout<<-1<<endl;
else cout<<ans<<endl;
}
return 0;
}
发表于 2020-08-25 16:43:45
回复(0)
import java.io.*;
// 创建一个 Point 类
class Point {
int a;
int b;
int x;
int y;
public Point(int a, int b, int x, int y) {
this.a = a;
this.b = b;
this.x = x;
this.y = y;
}
}
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());
StringBuilder sb = new StringBuilder();
for (int i = 0; i < n; i++) {
Point[] p = new Point[4]; // 用 p 来存放四个点
for (int j = 0; j < 4; j++) {
String[] line = br.readLine().split(" ");
p[j] = new Point(Integer.parseInt(line[0]),
Integer.parseInt(line[1]),
Integer.parseInt(line[2]),
Integer.parseInt(line[3]));
}
sb.append(minMove(p)).append("\n");
}
System.out.print(sb);
br.close(); // 关闭 io
}
public static int minMove(Point[] p) {
int move = 16;
for (int i = 1; i <= 4; i++) {
rotate(p[0]);
for (int j = 1; j <= 4; j++) {
rotate(p[1]);
for (int k = 1; k <= 4; k++) {
rotate(p[2]);
for (int v = 1; v <= 4; v++) {
rotate(p[3]);
if (isSquare(p)) {
move = Math.min(move, i%4 + j%4 + k%4 + v%4);
}
}
}
}
}
return move == 16 ? -1 : move;
}
// 原地修改
public static void rotate(Point point) {
int tmp = point.a;
point.a = point.x + point.y - point.b;
point.b = point.y - point.x + tmp;
}
// 找最长的边长和最短的边长，前者出现两次，后者出现四次且不为 0 ，则正方形成立
public static boolean isSquare(Point[] p) {
long min = Long.MAX_VALUE, max = Long.MIN_VALUE;
int count1 = 0, count2 = 0;
for (int i = 0; i < 4; i++) {
for (int j = i + 1; j < 4; j++) {
long dis = distance(p[i], p[j]);
if (dis > max) { max = dis; count1 = 1; }
else if (dis == max) count1++;
if (dis < min) { min = dis; count2 = 1; }
else if (dis == min) count2++;
}
}
return count1 == 2 && count2 == 4 && min != 0;
}
// 注意使用 long 类型防止溢出
public static long distance(Point p1, Point p2) {
return ((long) (p1.a - p2.a) * (p1.a - p2.a)
+ (p1.b - p2.b) * (p1.b - p2.b));
}
} 好像第一次写这么长的。。43ms
发表于 2020-05-13 20:04:55
回复(0)
JavaScript(Node) 😎题目:网易-整理房间（穷举）
const readline = require('readline');
const lines = [];
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout
});
let n = -1;
let pos1, pos2, pos3, pos4;
rl.on('line', function(line) {
lines.push(line.split(" ").map(i => Number(i)));
if(lines.length === 1) {
n = Number(lines[0][0]);
}
if(lines.length === 4*n+1) {
for(let i=0; i<n; i++) {
pos1 = lines[4*i+1];
pos2 = lines[4*i+2];
pos3 = lines[4*i+3];
pos4 = lines[4*i+4];
console.log(move(pos1, pos2, pos3, pos4));
}
}
});
function move(pos1, pos2, pos3, pos4){
let count = 16;
let p1, p2, p3, p4;
for(let j=0;j<4;j++) {
p1 = rotate(pos1, j);
for(let k=0;k<4;k++) {
p2 = rotate(pos2, k);
for(let l=0;l<4;l++) {
p3 = rotate(pos3, l);
for(let m=0;m<4;m++) {
p4 = rotate(pos4, m);
if(isSquare(p1, p2, p3, p4)) {
count = Math.min(count, j+k+l+m);
}
}
}
}
}
return count === 16 ? -1 : count;
}
function rotate(pos, times) {
var [a, b, x, y] = pos;
for(let i=1;i<=times;i++) {
var temp = a;
a = y-b+x;
b = temp-x+y;
}
// (a-x, b-y) => (y-b, a-x)
return [a, b, x, y];
}
function distance(pos1, pos2) {
return Math.pow(pos1[0]-pos2[0], 2) + Math.pow(pos1[1]-pos2[1], 2);
}
function isSquare(pos1, pos2, pos3, pos4) {
var q = [distance(pos1, pos2), distance(pos1, pos3), distance(pos1, pos4), distance(pos2, pos3), distance(pos2, pos4), distance(pos3, pos4)];
q.sort((a, b) => a-b);
if(q[0] !== 0 && q[0]===q[1] && q[1]===q[2] && q[2]===q[3] && q[4]===q[5] && q[4]===2*q[3]) {
return true;
}
return false;
}
发表于 2020-02-26 11:26:42
回复(0)
#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)
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
回复(4)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Main{
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.valueOf(in.readLine());
int[][][] things = new int[N][4][4];
for(int i=0;i<N;i++){
for(int j=0;j<4;j++){
String[] s = in.readLine().split(" ");
for(int k=0;k<4;k++){
things[i][j][k] = Integer.valueOf(s[k]);
}
}
}
for(int i=0;i<N;i++){
System.out.println(calcu(things[i]));
}
}
public static int calcu(int[][] thing){
int ans = 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 l=0;l<4;l++){
int[][] test = new int[4][4];
test[0] = rotate(thing[0],i);
test[1] = rotate(thing[1],j);
test[2] = rotate(thing[2],k);
test[3] = rotate(thing[3],l);
if(isSquare(test)){
ans = Math.min(ans,i+j+k+l);
}
}
}
}
}
return ans == Integer.MAX_VALUE? -1:ans;
}
public static int[] rotate(int[] p,int k){//旋转k次
int[] ans = Arrays.copyOf(p,4);
for(int i=0;i<k;i++){
int x0 = ans[2],y0 = ans[3],x1 = ans[0],y1 = ans[1];
int tmpX = x0 - (y1 - y0);
int tmpY = y0 + (x1 - x0);
ans[0] = tmpX;
ans[1] = tmpY;
}
return ans;
}
public static boolean isSquare(int[][] thing){//各个点不一定是顺序相连的,这样getDistance有可能是求得的对角线的值
//快速判断正方形的方法,正方形,加对角线6条,求出所有点之间的距离6个,从小到大排序,较小4个相等,较大2个相等
long[] arr = new long[6];
arr[0] = getDistance(thing[0],thing[1]);
arr[1] = getDistance(thing[0],thing[2]);
arr[2] = getDistance(thing[0],thing[3]);
arr[3] = getDistance(thing[1],thing[2]);
arr[4] = getDistance(thing[1],thing[3]);
arr[5] = getDistance(thing[2],thing[3]);
Arrays.sort(arr);
return arr[0] == arr[1]
&& arr[0] != 0 //注意,边长不能为0,否则可能出现重合到一点,移动的步数比较小.
&& arr[1] == arr[2]
&& arr[2] == arr[3]
&& arr[4] == arr[5];
}
public static long getDistance(int[] p1,int[] p2){
long xdis = Math.abs(p1[0]-p2[0]);
long ydis = Math.abs(p1[1]-p2[1]);
return xdis*xdis+ydis*ydis;
}
}
编辑于 2020-05-01 11:50:26
回复(0)
用直角判断isSquare
#include <iostream>
using namespace std;
struct Vec2i
{
Vec2i() : x(0), y(0) {}
Vec2i(int x, int y) : x(x), y(y) {}
int x;
int y;
};
Vec2i operator-(const Vec2i& p1, const Vec2i& p2) { return Vec2i(p1.x-p2.x, p1.y-p2.y); }
int distSq(const Vec2i& p) { return p.x*p.x + p.y*p.y; }
bool isRightAngle(const Vec2i& d1, const Vec2i& d2)
{
if (d1.x == 0 && d1.y == 0) return false;
if (d2.x == 0 && d2.y == 0) return false;
int dot = d1.x*d2.x + d1.y*d2.y;
return dot == 0;
}
bool isSquare(const Vec2i& p1, const Vec2i& p2, const Vec2i& p3, const Vec2i& p4)
{
Vec2i d12 = p2 - p1;
Vec2i d13 = p3 - p1;
Vec2i d14 = p4 - p1;
Vec2i d23 = p3 - p2;
Vec2i d24 = p4 - p2;
Vec2i d34 = p4 - p3;
int length12 = distSq(d12);
int length13 = distSq(d13);
int length14 = distSq(d14);
int length23 = distSq(d23);
int length24 = distSq(d24);
int length34 = distSq(d34);
if (isRightAngle(d13, d14) && length13 == length14 && isRightAngle(d23, d24) && length23 == length24)
return true; // 12 diagonal
if (isRightAngle(d12, d14) && length12 == length14 && isRightAngle(d23, d34) && length23 == length34)
return true; // 13 diagonal
if (isRightAngle(d12, d13) && length12 == length13 && isRightAngle(d24, d34) && length24 == length34)
return true; // 14 diagonal
return false;
}
Vec2i rotate90(const Vec2i& p, const Vec2i& center)
{
int dx = p.x - center.x;
int dy = p.y - center.y;
return Vec2i(-dy + center.x, dx + center.y);
}
void computeRotated(Vec2i rotated[4], const Vec2i& p, const Vec2i& center)
{
rotated[0] = p;
for (int i = 1; i < 4; ++i) rotated[i] = rotate90(rotated[i - 1], center);
}
int minRotationSteps(Vec2i p1, Vec2i p2, Vec2i p3, Vec2i p4, Vec2i c1, Vec2i c2, Vec2i c3, Vec2i c4)
{
Vec2i p1Rotated[4];
Vec2i p2Rotated[4];
Vec2i p3Rotated[4];
Vec2i p4Rotated[4];
// compute all rotated points
computeRotated(p1Rotated, p1, c1);
computeRotated(p2Rotated, p2, c2);
computeRotated(p3Rotated, p3, c3);
computeRotated(p4Rotated, p4, c4);
// find min steps
int min = 100;
for (int i1 = 0; i1 < 4; ++i1) {
for (int i2 = 0; i2 < 4; ++i2) {
for (int i3 = 0; i3 < 4; ++i3) {
for (int i4 = 0; i4 < 4; ++i4) {
int steps = i1 + i2 + i3 + i4;
if (steps < min && isSquare(p1Rotated[i1], p2Rotated[i2], p3Rotated[i3], p4Rotated[i4]))
min = steps;
}
}
}
}
if (min == 100) return -1; // no solutions
else return min;
}
int main()
{
int N;
cin >> N;
Vec2i p1, p2, p3, p4, c1, c2, c3, c4;
while (N--) {
cin >> p1.x >> p1.y >> c1.x >> c1.y;
cin >> p2.x >> p2.y >> c2.x >> c2.y;
cin >> p3.x >> p3.y >> c3.x >> c3.y;
cin >> p4.x >> p4.y >> c4.x >> c4.y;
cout << minRotationSteps(p1, p2, p3, p4, c1, c2, c3, c4) << endl;
}
return 0;
}
编辑于 2020-03-21 16:21:59
回复(0)
抄大佬的答案
import java.util.*;
public class Main{
private static Scanner sc;
public static void main(String[] args){
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++){
for(int k = 0;k<4;k++){
abxy[i][j][k] = sc.nextInt();
}
}
}
int min;
for(int i = 0;i<n;i++){
min = Integer.MAX_VALUE;
for(int cnt1 = 0;cnt1<4;cnt1++){
for(int cnt2 = 0;cnt2<4;cnt2++){
for(int cnt3 = 0;cnt3<4;cnt3++){
for(int cnt4 = 0;cnt4<4;cnt4++){
if(isSquare(rotate(abxy[i][0],cnt1),
rotate(abxy[i][1],cnt2),
rotate(abxy[i][2],cnt3),
rotate(abxy[i][3],cnt4)))
min = Math.min(min,cnt1+cnt2+cnt3+cnt4);
}
}
}
}
System.out.println(min == Integer.MAX_VALUE?-1:min);
}
}
private static int[] rotate(int[] nums,int times){
int[] res = new int[4];
if(times == 0)
return nums;
else{
res[2] = nums[2];
res[3] = nums[3];
res[0] = nums[2]-nums[1]+nums[3];
res[1] = nums[0]-nums[2]+nums[3];
return rotate(res,times-1);
}
}
private static boolean isSquare(int[] p1,int[] p2,int[] p3,int[] p4){
int px1 = p1[0],py1 = p1[1];
int px2 = p2[0],py2 = p2[1];
int px3 = p3[0],py3 = p3[1];
int px4 = p4[0],py4 = p4[1];
if((px1 ^ px2 ^ px3 ^ px4) != 0)
return false;
if((py1 ^ py2 ^ py3 ^ py4) != 0)
return false;
if(px1 == px2 && px1 == px3)
return false;
if(py1 == py2 && py1 == py3)
return false;
int edge1 = Math.abs((px1-px2) == 0?px1-px3:px1-px2);
int edge2 = Math.abs((py1-py2) == 0?py1-py3:py1-py2);
return edge1 == edge2;
}
}
发表于 2020-03-10 02:32:00
回复(0)
代码注释很详细，这里是一些基础知识，这种题要有耐心
（1）平面中，一个点(x,y)绕任意点(dx,dy)逆时针旋转a度后的坐标
xx= (x - dx)*cos(a) - (y - dy)*sin(a) + dx ;
yy= (x - dx)*sin(a) + (y - dy)*cos(a) +dy ;
#include<bits/stdc++.h> //万能的头文件 using namespace std; //Point类 typedef struct Point { //坐标 int x; int y; //绕着旋转的点 int a; int b; Point(int a1,int a2,int a3,int a4):x(a1),y(a2),a(a3),b(a4){} Point(){} }P;//一个点逆时针旋转n次的坐标 P rotate(P point,int times) { int x = point.x; int y = point.y; int a = point.a; int b = point.b; for(int i = 1;i<=times;i++) { int xx = a+b-y; int yy = x+b-a; x = xx; y = yy; } return Point(x,y,a,b); } //判断直角，向量p1p2乘以向量p1p3,结果为0，则两段垂直 bool is_Angle(P p1,P p2,P p3) { return ((p2.x-p1.x)*(p3.x-p1.x)+(p2.y-p1.y)*(p3.y-p1.y))==0; } //两点距离，这里测试用例都是整数 int distance(P p1,P p2) { return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y)); } //判断是正方形 bool is_Square(P p1,P p2,P p3,P p4) { //保存到数组中 vector<Point> nums(4); nums[0] = p1; nums[1] = p2; nums[2] = p3; nums[3] = p4; //要排序的，排序后就知道4个坐标的位置顺序 sort(nums.begin(),nums.end(),[](P a,P b){ return a.x==b.x?a.y<b.y:a.x<b.x; }); int d1 = distance(nums[0],nums[1]); int d2 = distance(nums[0],nums[2]); int d3 = distance(nums[1],nums[3]); int d4 = distance(nums[2],nums[3]); //这里要判断4段距离相等且不为0，一个角为90°，就是正方形 if(d1!=0&&d1==d2&&d2==d3&&d3==d4&&is_Angle(nums[0],nums[1],nums[2])) return true; else return false; } int main(void) { int n; cin>>n; vector<Point> nums(4); for(int i = 0;i<n;i++) { for(int j =0;j<4;j++) cin>>nums[j].x>>nums[j].y>>nums[j].a>>nums[j].b; int count = INT_MAX; //四重循环，每个点最多转3次，起始循环不大 for(int m=0;m <4;m++) for(int n=0;n <4;n++) for(int k=0;k <4;k++) for(int l=0;l <4;l++) { //旋转后是正方形，则记录 if(is_Square(rotate(nums[0],m),rotate(nums[1],n),rotate(nums[2],k),rotate(nums[3],l))) { count = min(count,m+n+k+l); } } //输出最小值 count = count==INT_MAX?-1:count; cout<<count<<endl; } return 0; }
发表于 2020-03-05 00:31:13
回复(1)
问题信息
通过挑战的用户
查看代码-
2022-08-27 19:11:34
-
2022-08-23 14:17:36 -
2022-08-20 14:52:26 -
2022-08-12 14:29:21
-
2022-06-23 15:32:38
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
