백준13423 - Three Dots

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

13423번: Three Dots

아무리 코드를 바꿔봐도 시간초과가 났었던 문제다. 잘 생각해보니까 정렬된 원소를 주었다. 그래서 이분탐색을 이용하면 시간초과가 나지 않겠구나 싶었다. 문제는 출발 위치 - 첫번째 점 - 두번째 점 사이의 간격이 같은 점들을 찾아서 총 몇가지의 경우가 나오는지 세는 것이다. 첫번째 점의 위치를 골랐다면 출발위치에서 첫번째 위치 사이의 거리를 구한 후 두번째 점의 위치는 방금 구한 거리에서 첫번째 점의 위치를 더한 것이다. 효율적이게 출발위치에서 마지막 점까지의 절반 위치를 구해놓고 절반 위치 길이보다 현재 설정한 첫번째 점의 위치까지의 길이가 길면 탐색을 중단한다.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
	int n; //원하는 테스트 케이스의 수
	cin >> n;
	while (n--) {
		int num = 0, cnt = 0; //벡터의 넣을 원소 num, 가능한 좌표의 3개 모음 갯수 cnt
		double mid; //현재 주어진 범위에서 중간 거리
		vector<int> v; //점의 위치

		//벡터의 원소를 받은 뒤 오름차순으로 정렬
		cin >> num;
		for (int i = 0; i < num; i++) {
			int what;
			cin >> what;
			v.push_back(what);
		}
		sort(v.begin(), v.end());

		//좌표 양 끝을 기준으로 
		for (int i = 0; i < v.size() - 1; i++) {
			mid = (v[v.size() - 1] - v[i]) / 2.0; //시작점에서 끝 점까지의 절반 길이를 구한다.
			for (int j = i + 1; j < v.size(); j++) {
				double len = v[j] - v[i]; //첫번째 점에서 두번째 점까지의 거리를 구한다.
				if (len > mid) { //중간 길이보다 현재 구한 길이가 길면 
					break; //탐색을 안한다.
				}
				else { //그 외의 경우는 이분탐색을 통해 실제로 있는 점인지 찾는다.
					int what = v[j] + len; //두번째 위치는 첫번째 점에서 len을 더한 값이다.
					int l = i;
					int r = v.size() - 1;
					while (l <= r) {
						int m = (l + r) / 2;
						if (v[m] == what) { //실제로 있는 점이면
							cnt++; //경우의 수를 증가
							break;
						}
						else if (v[m] < what) {
							l = m + 1;
						}
						else {
							r = m - 1;
						}
					}
				}
			}
		}
		cout << cnt << '\n';
 	}
}