[백준온라인] 27516번 과녁 맞추기

문제 : https://www.acmicpc.net/problem/27516

27516번: 과녁 맞추기

 

문제 요약 : 특정 속도로 던졌을 때 맞출 수 있는 과녁의 최대 개수 출력

 

C++

소스코드 : https://github.com/cbkpar/BOJ/blob/main/boj_27516.cpp

채점 번호	아이디	문제 번호	결과	메모리	시간	언어	코드 길이
56641730	cbkpar	27516	맞았습니다!!	5232KB	56ms	C++17	2177B

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

long long gcd(long long lA, long long lB)
{
	if (lB % lA == 0) return lA;
	return gcd(lB % lA, lA);
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	long long lX, lY;
	cin >> lX >> lY;

	vector<pair<long long, long long>> vecMinus;
	vector<pair<long long, long long>> vecPlus;

	int iN;
	cin >> iN;
	while (iN--)
	{
		long long lTempX, lTempY;
		cin >> lTempX >> lTempY;

		lTempX -= lX;
		lTempY -= lY;
		if (lTempX == 0 || lTempY >= 0) continue;

		if (lTempX < 0)
		{
			lTempX = abs(lTempX) * abs(lTempX);
			lTempY = abs(lTempY);
			long long lGCD = (lTempX < lTempY ? gcd(lTempX, lTempY) : gcd(lTempY, lTempX));
			lTempX /= lGCD;
			lTempY /= lGCD;
			vecMinus.push_back({ lTempX, lTempY });
		}
		else
		{
			lTempX = abs(lTempX) * abs(lTempX);
			lTempY = abs(lTempY);
			int lGCD = (lTempX < lTempY ? gcd(lTempX, lTempY) : gcd(lTempY, lTempX));
			lTempX /= lGCD;
			lTempY /= lGCD;
			vecPlus.push_back({ lTempX, lTempY });
		}
	}

	int iAns = 0;
	if (vecMinus.size() > 0)
	{
		sort(vecMinus.begin(), vecMinus.end(), [](pair<long long, long long> o1, pair<long long, long long> o2)->bool
			{
				if (o1.first == o2.first)
				{
					return o1.second < o2.second;
				}
				return o1.first < o2.first;
			});

		iAns = max(iAns, 1);
		int iCount = 1;
		int iSize = vecMinus.size();
		for (int i = 1; i < iSize; ++i)
		{
			if (vecMinus[i].first == vecMinus[i - 1].first && vecMinus[i].second == vecMinus[i - 1].second)
			{
				++iCount;
			}
			else
			{
				iCount = 1;
			}
			iAns = max(iAns, iCount);
		}
	}
	if (vecPlus.size() > 0)
	{
		sort(vecPlus.begin(), vecPlus.end(), [](pair<long long, long long> o1, pair<long long, long long> o2)->bool
			{
				if (o1.first == o2.first)
				{
					return o1.second < o2.second;
				}
				return o1.first < o2.first;
			});
		iAns = max(iAns, 1);
		int iCount = 1;
		int iSize = vecPlus.size();
		for (int i = 1; i < iSize; ++i)
		{
			if (vecPlus[i].first == vecPlus[i - 1].first && vecPlus[i].second == vecPlus[i - 1].second)
			{
				++iCount;
			}
			else
			{
				iCount = 1;
			}
			iAns = max(iAns, iCount);
		}
	}
	cout << iAns << "\n";
	return 0;
}

 

과녁의 위치에서 사격자의 위치를 빼서 상대위치로 변환해준다.

 

발사자는 x축에 평행하게 던지므로 x값이 0인 경우를 제외 한다.

중력이 작용하기 때문에 y값이 0과 같거나 큰 경우를 제외 한다.

 

x의 위치가 음수인 경우는 양수인 경우와 동시에 맞출 수 없다.

마찬가지로 양수인 경우는 음수인 경우와 동시에 맞출 수 없다.

그러므로 두개의 집합으로 따로 생각 해 준다.

 

t(시간) 이후 X와 Y의 좌표는 다음과 같다.

x = v_x * t

y = 0.5 * g * t^2

 

따라서 v_x의 속도로 발사 했을 때 저 그래프에 있는 과녁은 모두 동시에 맞게 된다.

이것을 확인하기 위해 x를 제곱하여 선형적으로 확인 할 수 있게 한다

즉, x^2/y 값이 같은 경우 동시에 맞는다 이것을 기약분수로 나타내기 위해

유클리드 호제법을 이용해 분모분자를 나누고 기록 해둔다

 

기록한 값들을 내림차순 혹은 오름차순으로 정리하고

같은 개수를 체크 해 가장 많은 개수가 나온 경우를 출력한다