[백준] 1485 정사각형 - 기하학(Geometry) + 정렬(Sorting) JAVA

https://www.acmicpc.net/problem/1485

코드설명

기하학(Geometry) + 정렬(Sorting)을 활용합니다.

 

정사각형의 특성을 활용합니다.

특이사항은, 아래의 함수를 보면 두 점 사이 간의 직선거리가 아닌, 점을 몇개를 거쳐서 갈 수 있느냐를 구하고 있습니다.

public static double getDistance(Point p1, Point p2) {
    double rD = p1.r - p2.r;
    double cD = p1.c - p2.c;

    double Diff = Math.sqrt( Math.pow(rD, 2) ) + Math.sqrt( Math.pow(cD, 2));
    return Diff;
}

만약, 점과 점 사이의 직선거리를 구한다면, 한번에 sqrt로 제곱근을 구해야 합니다.

double Diff = Math.sqrt( Math.pow(rD, 2) + Math.pow(cD, 2));

 

이 문제에서는 정사각형을 구하는것이 목표였으므로, 대각선 간의 거리가 같기만 하면 되니, 점과 점 사이의 최단 점 거리를 구하는 방식으로도 성공합니다. 

혹은 정사각형의 특성으로 대각선의 길이 = 2 * 일반변 이므로,

대각선의 길이가 일반변의 * 2 인지 확인하는 과정으로도 가능합니다.

코드

정답코드입니다.

package Main;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    private static int N, T, M; 
    private static int answer = 0;
    private static Point[] point;
    public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		T = Integer.parseInt(st.nextToken());
		while(T-- > 0) {
			point = new Point[4];
			double[] distance = new double[6];
			for(int i=0;i<4;i++) {
				st = new StringTokenizer(br.readLine());
				point[i] = new Point(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
			}
			
			getDistance(point[0], point[1]);
			int dIdx = 0;
			for(int i=0; i<4; i++) {
				for(int j=i+1; j<4; j++) {
					distance[dIdx++] = getDistance(point[i], point[j]);  
				}
			}
			
			Arrays.sort(distance);
			
			if( distance[0] == distance[1] 
				&& distance[1] == distance[2]
				&& distance[2] == distance[3]
				&& distance[4] == distance[5]
			) {
				System.out.println(1);
			}else {
				System.out.println(0);
			}
				
		}
		
	}
    
    public static double getDistance(Point p1, Point p2) {
    	double rD = p1.r - p2.r;
    	double cD = p1.c - p2.c;
    	
    	double Diff = Math.sqrt( Math.pow(rD, 2) ) + Math.sqrt( Math.pow(cD, 2));
    	return Diff;
    }
    
    private static class Point{
    	int r;
    	int c;
    	public Point(int r, int c) {
    		this.r = r;
    		this.c = c;
    	}
    }
    
}

 

 

처음에 풀었던 접근이 틀린 코드입니다.

각 변이 일직선인지, 그리고 같은 길이인지를 비교했습니다. 

하지만, 이렇게 하면 만약 정사각형이 45도 기울어져있는 경우는 고려하지 못합니다. 

제가 처리한 방식은 정사각형이 우리가 일반적으로 생각하는 정사각형인 경우만 작동합니다. (가로에 평행인 정사각형을 의미합니다.)

package Main;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;

public class Main {
    private static int N, T, M; 
    private static int answer = 0;
    private static Point[] point;
    public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		T = Integer.parseInt(st.nextToken());
		while(T-- > 0) {
			point = new Point[4];
			for(int i=0;i<4;i++) {
				st = new StringTokenizer(br.readLine());
				point[i] = new Point(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
			}
			
			Arrays.sort(point);
			
			boolean isSuccess = false;
			int standardLength = point[1].y - point[0].y;
			//길이를 먼저 구한다.
			//만약 행이 같거나, 열이 다르다면, 실패.
			if(point[0].x == point[1].x && point[0].y < point[1].y && point[1].y - point[0].y == standardLength) {
				
				if(point[0].x < point[2].x && point[0].y == point[2].y && point[2].x - point[0].x == standardLength) {
					
					if(point[2].x == point[3].x && point[2].y < point[3].y && point[3].y - point[2].y == standardLength) {
						
						if(point[1].x < point[3].x && point[1].y == point[3].y && point[3].x - point[1].x == standardLength) {
							isSuccess = true;
						}
						
					}
					
				}
			}
			
			if(isSuccess == false) System.out.println("0");
			else System.out.println("1");
		}
		
	}
    
    private static class Point implements Comparable<Point>{
    	private int x;
    	private int y; 
    	
    	@Override
    	public int compareTo(Point other) {
    		if(this.x != other.x) {
    			return Integer.compare(this.x, other.x);
    		}
    		return Integer.compare(this.y, other.y);
    	}
    	
    	public Point(int x, int y) {
    		this.x = x;
    		this.y = y;
    	}
    }
    
    
}