백준(BOJ) 16192 Voronoi Diagram Returns *

# 단순 구현

영어여서 어려워 보이는 것이고 n, q의 범위가 작아서

query 한 점과 모든 n 점에 대해서 비교하여 거리가 가장 작은 점의 갯수가

(예를들어, 거리가 3이 가장 작다면 3인점이 여러개가 있을 수 이싸.)

1개면 REGION

2개면 LINE

3개 이상이면 POINT가 됩니다.

아 그리고 NONE인 경우는 나올 수가 없다.

# 실수 했던 점

3개가 아니고 3개 이상이어야 한다^^;

#include<iostream>
#include<cstdio>
#include<cmath>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;

int n, m;
pair<int, int > p[2005], q[250005];

int fun(int x1, int y1, int x2, int y2)
{
	int x = x1 - x2, y = y1 - y2;
	return x*x + y*y;
}

int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 0; i < n; i++)
		scanf("%d%d", &p[i].first, &p[i].second);
	for (int i = 0; i < m; i++)
		scanf("%d%d", &q[i].first, &q[i].second);

	for (int i = 0; i < m; i++)
	{
		int mi = 2123456789;
		int ans = 0;
		vector<int> region;
		for (int j = 0; j < n; j++)
		{
			int tmp = fun(q[i].first, q[i].second, p[j].first, p[j].second);
			if (tmp < mi)
			{
				mi = tmp;
				ans = 1;
				region.clear();
				region.push_back(j);
			}
			else if (tmp == mi)
			{
				ans++;
				region.push_back(j);
			}
		}

		sort(region.begin(), region.end());

		if (ans == 0)
			printf("NONE");
		else if(ans == 1)
		{
			printf("REGION ");
			for (int j = 0; j < region.size(); j++)
				printf("%d ",region[j]+1);
		}
		else if (ans == 2)
		{
			printf("LINE ");
				for (int j = 0; j < region.size(); j++)
					printf("%d ", region[j]+1);
		}
		else if (ans >= 3)
		{
			printf("POINT ");
		}
		printf("\n");
	}
	return 0;
}