글 읽기 - 모노톤길 도와주세요 ...

umc1997 5년 전 0

제 알고리즘은 좌표를 x오름차순정렬(x값이 같으면 y값오름차순)을 하고
cnt를 돌리는데 한 기준점과 그 다음점은
(1)x값이 같거나
(2)y값이 같거나
(3)x,y값이 둘다 같지 않는
경우 3가지가 있는데 (1),(2)는 그냥 cnt++해주고 (3)인 경우는 기준점 다음에서부터 기준점y값과 같은 y값을 가지는 점을 찾고 그 구간을 반대로 뒤집어 줘서 길을 이었습니다.

어디가 문제일까요?

#include <iostream>
#include <fstream>
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <utility>

using namespace std;


int main()
{
	ifstream in;
	in.open("input.txt");
	int test = 0;
	in >> test;
	for (int l = 0; l < test; l++)
	{
		int n;
		in >> n;
		vector<pair<int, int>> cafe;
		for (int i = 0; i < n; i++)
		{
			int x, y;
			in >> x >> y;
			cafe.push_back(make_pair(x, y));
		}
		sort(cafe.begin(), cafe.end());
		int cnt = 0;
		while (cnt < n - 1)
		{
			// x좌표나 y좌표가 같으면 길이 이어진 것으로 간주
			if (cafe[cnt].first == cafe[cnt + 1].first)
			{
				cnt++;
			}
			else if (cafe[cnt].second == cafe[cnt + 1].second)
			{
				cnt++;
			}
			// x좌표도 다르고 y좌표도 다르면 x좌표같은 것의 순서를 reverse
			else
			{
				int tmp = cnt + 1;
				int endY = cafe[tmp].second;
				while (tmp<n)
				{
					if (endY == cafe[cnt].second)
					{
						break;
					}
					tmp++;
					endY = cafe[tmp].second;
				}
				int p = cnt + 1;
				int q = tmp;
				//reverse algorithm
				while (q > p)
				{
					pair<int, int> tmpPair;
					tmpPair = cafe[p];
					cafe[p] = cafe[q];
					cafe[q] = tmpPair;
					p++;
					q--;
				}
				cnt = tmp;
			}
		}
		int m;
		in >> m;
		for (int i = 0; i < m; i++)
		{
			int check;
			in >> check;
			cout << cafe[check - 1].first << " " << cafe[check - 1].second << endl;
		}

	}
	return 0;
}

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

문제

문제

출처

ICPC

모노톤길 도와주세요 ...

umc1997 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말