글 읽기 - 댓글에 있는 케이스들 다 맞는데 틀렸습니다.. 고수분들 도와주십시오(주석있습니다)

mistcase 7년 전 3

진행없이 채점하자마자 틀렸습니다가 바로나와 문의드립니다.

long long으로 바꾸어보아도.. 게시판하나하나 읽어가며 테스트케이스는 다 집어넣어도 맞게 나오는 것 같아 문의 남깁니다 ㅜㅜ...

시작점과 끝점으로 선분을 만들어 벡터에 저장 후

선분과 새로진행할 선분이 교차하는지 판별하는 방법입니다.

도와주십시오 고수님들.

사용한 테스트케이스들과 답 입니다

11
100000000
5
100000000 L
100000000 L
200000000 L
199999999 L
199999999 L
1
6
1 L
1 L
2 L
2 L
2 L
3 L
1
0
4
6
2 L
1 R
1 R
3 R
2 R
1 L
3
1
1L
3
4
2 L
2 L
1 L
5 R
3
3
2 L
4 L
4 R
4
4
1 L
1 L
2 L
1 L
3
3
1 L
1 L
2 L
4
5
1 L
1 R
1 R
1 R
10 L
8
11
1 L
4 R
1 R
8 L
1 L
8 R
1 R
8 L
1 L
6 L
10 R

답
899999997
9
2
16
5
7
6
6
9
5
40

#include <iostream>
#include <vector>
#include <cmath>
typedef long long lld;
using namespace std;
lld arrstatus[5] = { 0 }; //상태저장 배열 현재x좌표, y좌표, 머리방향, 시간, Gameover여부
int maxxy; //L*2+1 크기의 격자판 왼쪽 아래를 0,0으로 지정 스타트지점은 L,L로 설정

struct Point {
	lld x;
	lld y;
	Point() {}
	Point(lld a, lld b) {
		x = a; y = b;
	}
};
struct Line {
	Point pt1;
	Point pt2;
	Line() {}
	Line(Point a, Point b) {
		pt1 = a; pt2 = b;
	}
};

bool isinpool(Point endpt) {
	if (endpt.x < maxxy && endpt.x >= 0) {
		if (endpt.y < maxxy && endpt.y >= 0)
			return true;
	}
	return false;
}
// 세 점의 상대적 위치 결정
lld direction(Point A, Point B, Point C) {
	lld dxAB, dxAC, dyAB, dyAC, dir;
	dxAB = B.x - A.x;
	dyAB = B.y - A.y;
	dxAC = C.x - A.x;
	dyAC = C.y - A.y;
	dir = 0;
	if (dxAB * dyAC < dyAB * dxAC) dir = 1;
	if (dxAB * dyAC > dyAB * dxAC) dir = -1;
	if (dxAB * dyAC == dyAB * dxAC) //일직선상에 있는경우
	{
		if (dxAB == 0 && dyAB == 0) dir = 0; //A=B
		else if ((dxAB * dxAC < 0) || (dyAB * dyAC < 0)) dir = -1; // A가 가운데
		else if (dxAB * dxAB + dyAB * dyAB >= dxAC * dxAC + dyAC *dyAC) dir = 0; //C가가운데
		else dir = 1; // B가 가운데
	}
	return dir;
}

//두 선분 교차 여부 (AB, CD가 서로 교차하면 T)
bool intersection(Line AB, Line CD) {
	bool lineCrossing;
	if ((direction(AB.pt1, AB.pt2, CD.pt1) * direction(AB.pt1, AB.pt2, CD.pt2) <= 0) && (direction(CD.pt1, CD.pt2, AB.pt1) * direction(CD.pt1, CD.pt2, AB.pt2) <= 0))
	{
		lineCrossing = true;
	}
	else
		lineCrossing = false;
	return lineCrossing;
}
//점과 직선사이 거리
lld caldistance(Point P, Line AB) {
	lld x1 = AB.pt1.x;
	lld y1 = AB.pt1.y;
	lld x2 = AB.pt2.x;
	lld y2 = AB.pt2.y;
	if (x1 == x2 && P.x != x2) {
		return abs(P.x - x1);
	}
	else if (y1 == y2 && P.y != y2) {
		return abs(P.y - y2);
	}
	else {
		if (y1 == P.y)   //가로선분과 같은직선에놓인 점
			return abs(P.x - x2) <= abs(P.x - x1) ? abs(P.x - x2) : abs(P.x - x1);
		else
			return abs(P.y - y2) <= abs(P.y - y1) ? abs(P.y - y2) : abs(P.y - y1);
	}
}

int main() {
	freopen("input.txt", "r", stdin);
	int T;
	cin >> T;
	for(int tc=0; tc<T; tc++){
	int NumL, NumN, time, tmp;
	char dir = 'N';
	vector<Line> saveline;
	vector<Line> crash;
	vector<int> timearr;
	vector<char> dirarr;
	saveline.clear();
	crash.clear();
	timearr.clear();
	dirarr.clear();
	cin >> NumL >> NumN;
	maxxy = 2 * NumL + 1;
	if (NumN == 0) {
		timearr.push_back(maxxy);
		dirarr.push_back(dir);
	}
	for (int i = 0; i<NumN; i++) {
		cin >> time >> dir;
		timearr.push_back(time);
		dirarr.push_back(dir);
	}

	arrstatus[0] = arrstatus[1] = NumL; //시작좌표 L,L
	arrstatus[2] = 0;   //방향 오른쪽
	arrstatus[3] = 0;   //시간0초
	arrstatus[4] = 1;   //게임진행가능

	Point ept(NumL + timearr.at(0), NumL);
	Point spt(NumL, NumL);
	//0번테스트케이스만 별도 진행
	if (isinpool(ept)) {
		arrstatus[3] += timearr.at(0);
		if (dirarr.at(0) == 'L') arrstatus[2] = (arrstatus[2] + 1) % 4;
		else if (dirarr.at(0) == 'R') arrstatus[2] = (arrstatus[2] + 5) % 4;
		saveline.push_back(Line(spt, ept));
	}
	else {
		cout << maxxy - NumL << endl;
		//return 0;
		continue;
	}
	//1번테스트케이스부터 반복
	int t = 1;
	while (arrstatus[4] != 0) {
		if (--NumN > 0) {
			time = timearr.at(t);
			dir = dirarr.at(t++);
		}
		else {
			time = maxxy;
			dir = 'N';
		}
		spt = ept;

		switch (arrstatus[2]) { //도착점 설정 
		case 0: //Right
			ept.x = spt.x + time;
			ept.y = spt.y;
			tmp = maxxy - spt.x; //몸통 충돌없이 도착점이 밖으로 나갔을 경우 계산에 사용할 변수
			break;
		case 1: //Up
			ept.x = spt.x;
			ept.y = spt.y + time;
			tmp = maxxy - spt.y;
			break;
		case 2: //Left
			ept.x = spt.x - time;
			ept.y = spt.y;
			tmp = spt.x + 1;
			break;
		case 3: //Down
			ept.x = spt.x;
			ept.y = spt.y - time;
			tmp = spt.y + 1;
			break;
		}

		Line AB(spt, ept);
		//방향전환
		if (dir == 'L') arrstatus[2] = (arrstatus[2] + 1) % 4;
		else if (dir == 'R') arrstatus[2] = (arrstatus[2] + 3) % 4;

		//기존선분들과 충돌하는지 검사
		for (int i = saveline.size() - 2; i >= 0; i--) {
			if (intersection(AB, saveline.at(i)) == true) {
				arrstatus[4] = 0;
				crash.push_back(saveline.at(i)); //가장가까운 선분을 고르기위해 벡터에 저장
			}
		}
		if (arrstatus[4]) {   // 몸통이랑 충돌이 없는경우
			if (isinpool(ept)) {
				arrstatus[3] += time;
				if (NumN >= 0)	saveline.push_back(AB);
			}
			else {  //범위밖인경우
				arrstatus[3] += tmp;
				arrstatus[4] = 0;
			}
		}
		else {  //몸통이랑 충돌있는경우
			lld mindis = maxxy + 1;
			for (int i = 0; i<crash.size(); i++) { //충돌한 선분들중 가장 가까운 선분 가려내기
				mindis = (mindis >= caldistance(spt, crash.at(i))) ? caldistance(spt, crash.at(i)) : mindis;
			}
			arrstatus[3] += mindis;
			arrstatus[4] = 0;
		}
	}
	// 출력
	cout << arrstatus[3] << endl;

	}
	return 0;
}

bbrightsoon 7년 전 1

2번 케이스 틀리신것같은데 다시생각해보세요!

bbrightsoon 7년 전 1

1. 100000000(동)

2. 100000000(북)

3. 200000000(서)

4. 199999999(남)

5. 199999999(동)

6. 부딪힐때까지 = X(북)

다 더해서 써보면,

답 = 1억 + 1억 + 2억 + (2억 - 1) + (2억 - 1) + X

= 8억 - 2 + X

인데 6번 과정에서 1번 선분이랑 부딪히게 되니까 X = 1억 - 1이 되죠 그러므로

답 = 9억 - 3 = 899999997 입니다

mistcase 7년 전 0

@bbrightsoon 님 설명 감사드립니다.

곱하기가 범위밖으로나가서 값이 잘못 나오고 있었습니다 ㅜㅜ

long long으로 가져가니 899999997 잘나오는데

여전히 틀렸습니다.. 다시 고민해봐야겠습니다 .

답변 감사드립니다.

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

문제

문제

출처

ICPC

댓글에 있는 케이스들 다 맞는데 틀렸습니다.. 고수분들 도와주십시오(주석있습니다)

mistcase 7년 전 3

bbrightsoon 7년 전 1

bbrightsoon 7년 전 1

mistcase 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말