글 읽기 - 1064번 평행사변형 질문입니다.

nayuta9010 9년 전 0

아이디어가 잘못됬는지 궁금해서 질문합니다.

우선 -1 평행사변형을 이룰 수 없는 경우가 모든점이 한 직선 위에 있을 때 인 경우인데요

a,b,c 세점이 있다고 가정하면 a,b 직선의 기울기와 a,c 직선의 기울기 , b,c직선의 기울기가 같을 경우 -1을 출력했습니다.

그 다음 가장 큰 평행사변형은 가장 짧은 직선이 겹치는 경우고, 가장 작은 평행사변형은 가장 긴 직선이 겹치는 경우로 생각하고 둘레를 구했는데.. 계속 오답이 나옵니다.. ㅠㅠ

아이디어가 잘못된건가요? 아니라면 테스트 해볼만한 반례같은게 있을까요 ㅠㅠ

(코드가 깁니다.. 죄송해요 ㅠㅠ)

#include <iostream>
#include <math.h>
#include <stdio.h>

using namespace std;

bool Compare(); //true : 하나라도 다른경우, false : 세각이 모두 같은경우
void getDistance(int x1, int y1, int x2, int y2, int num); //각 점과 점 사이의 거리를 구하는 함수
void getMaxMin(); //가장 긴 선분을 가지고 있는 배열 번호와 가장 짧은 선분을 가지고 있는 배열의 번호를 구하는 함수
void getPerimeter(); //실제 둘레를 구하는 함수

double arrDistance[3]; //[0] = ab, [1] = bc, [2] = ac // 각 점과 점 사이의 거리를 저장한 배열
int maxNum = 0, minNum = 0; //getMaxMin 함수에서 구하는 두 값을 저장하는 변수
int aX, aY, bX, bY, cX, cY; //각 좌표를 저장하는 변수
long double maxL, minL; //가장 긴 선분의 길이와 가장 짧은 선분의 길이

int main()
{
	bool bAngle;

	cin >> aX >> aY >> bX >> bY >> cX >> cY; //입력받고

	bAngle = Compare(); //기울기 비교하고

	if (bAngle) //기울기가 다른경우 진입
	{
		for (int i = 0; i < 3; i++) //선분의 길이를 구하기 위한 반복
		{
			switch (i)
			{
			case 0:
				getDistance(aX, aY, bX, bY, i);
				break;
			case 1:
				getDistance(bX, bY, cX, cY, i);
				break;
			case 2:
				getDistance(cX, cY, aX, aY, i);
				break;
			}
		}
		getMaxMin();
		getPerimeter();

		printf("%.10Lf\n", maxL * 2 - minL * 2);
		//cout << maxL * 2 - minL * 2 << endl;
	}
	else //기울기가 같은 경우
	{
		cout << -1 << endl;
	}

	return 0;
}

bool Compare()
{
	double angle1, angle2, angle3; //각 선분의 기울기
	if ((aY == bY && bY == cY) || (aX == bX && bX == cX)) //각 좌표의 x값 또는 y값이 모두 같은경우 한 직선위에 있는 경우 이므로
	{
		return false; //기울기가 같음
	}
	else if (aX != bX && bX != cX) //0으로 나누면 안되므로 조건 삽입
	{
		angle1 = (aY - bY) / (aX - bX); //ab의 기울기
		angle2 = (bY - cY) / (bX - cX); //bc의 기울기
		angle3 = (aY - cY) / (aX - cX); //ac의 기울기
	}
	else { return true; } //이경우는 x의 값이 두개는 같고 하나는 다른경우인데 이 경우는 무조건 삼각형 성립가능 (서로 다른 점이 주어지기 때문에)

	if (angle1 == angle2 && angle2 == angle3) //세 기울기가 모두 같은경우는 한 직선상에 있으므로 삼각형 성립 불가능
	{
		return false;
	}
	return true; //나머지 경우는 가능
}

void getDistance(int x1, int y1, int x2, int y2, int num)
{
	arrDistance[num] = pow((x1 - x2), 2) + pow((y1 - y2), 2); //제곱해서 각각의 배열에 삽입 (피타고라스정리)
}

void getMaxMin()
{
	double iMax = arrDistance[0]; //최대값을 0번이라고 가정
	double iMin = arrDistance[0]; //최소값을 0번이라고 가정

	for (int i = 1; i < 3; i++)
	{
		maxNum = (arrDistance[i] > iMax) ? i : maxNum; //다음 배열값이 최대값 보다 크면 최대값의 배열 번호 교체 아닌경우 현상유지
		minNum = (arrDistance[i] < iMin) ? i : minNum; //다음 배열값이 최소값 보다 작으면 최소값의 배열 번호 교체 아닌경우 현상유지
	}
}

void getPerimeter()
{
	for (int i = 0; i < 3; i++) //배열을 돌리기 위한 반복문
	{
		if (i != minNum) //최소값만 제외하고 모두 더함
		{
			maxL += sqrt(arrDistance[i]); //평행사변형이 제일 클때 둘레 길이 (반쪽)
		}
		if (i != maxNum) //최대값만 제외하고 모두 더함
		{
			minL += sqrt(arrDistance[i]); //평행사변형이 제일 작을때 둘레 길이 (반쪽)
		}
	}
}

portableangel 9년 전 1

0 0 10 10 10 9

0 0 1 7 2 6

위와 같은 케이스들이 반례가 될 수 있는듯 합니다

nayuta9010 9년 전 0

반례가 전부 제대로 출력되는 것 같은데 .. 이유를 모르겠습니다. 후..

뭔가 정확도 문제인것 같기도 하고..

portableangel 9년 전 1

현재 0 0 10 10 10 9에서 1.3770... 을 출력하시는데, 답은 (아마도) 26이 넘어가게 됩니다.

그림은 조악하지만, 가장 큰 평행사변형은 대충 이렇게 생겼어요

nayuta9010 9년 전 0

요부분 수정해서 문제는 해결했는데 오답이네요..

아무래도 이번엔 정확도 문제이지 싶어요 ㅠㅠ

void getMaxMin()
{
	double iMax = arrDistance[0]; //최대값을 0번이라고 가정
	double iMin = arrDistance[0]; //최소값을 0번이라고 가정
	maxNum = 0, minNum = 0;

	for (int i = 1; i < 3; i++)
	{
		if (arrDistance[i] > iMax) //다음 배열값이 최대값 보다 크면 최대값의 배열 번호 교체 아닌경우 현상유지
		{
			iMax = arrDistance[i];
			maxNum = i;
		}
		if (arrDistance[i] < iMin)//다음 배열값이 최소값 보다 작으면 최소값의 배열 번호 교체 아닌경우 현상유지
		{
			iMin = arrDistance[i];
			minNum = i;
		}
	}
}

nayuta9010 9년 전 0

조언 감사합니다 (--)(__)(--)

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

1064번 평행사변형 질문입니다.

nayuta9010 9년 전 0

portableangel 9년 전 1

nayuta9010 9년 전 0

portableangel 9년 전 1

nayuta9010 9년 전 0

nayuta9010 9년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말