제출 #1160100

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1160100		xnqs	원 고르기 (APIO18_circle_selection)	C++20	컴파일 에러	0 ms	0 KiB

circle_selection

#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <cmath>
#include <unordered_map>
#include <unordered_set>

struct Circle {
	int64_t x, y, r, idx;
	Circle():
		x(0), y(0), r(0), idx(0) {}
	Circle(int64_t x, int64_t y, int64_t r, int64_t idx):
		x(x), y(y), r(r), idx(idx) {}
};

int64_t n;
std::vector<Circle> circles;
std::vector<int64_t> eliminator;

int64_t64_t grid_size;
std::unordered_map<int64_t, std::unordered_map<int64_t, std::vector<Circle>>> grid;

inline int64_t64_t euclid_dist(const Circle& a, const Circle& b) {
	return 1LL*(a.x-b.x)*(a.x-b.x) + 1LL*(a.y-b.y)*(a.y-b.y);
}

/*
	d(a,b) - a.r <= b.r
	sqrt((a.x-b.x)^2 + (a.y-b.y)^2) - a.r <= b.r
	sqrt((a.x-b.x)^2 + (a.y-b.y)^2) <= b.r + a.r
	(a.x-b.x)^2 + (a.y-b.y)^2 <= (b.r + a.r)^2
*/
inline bool int64_tersect(const Circle& a, const Circle& b) {
	return euclid_dist(a,b) <= 1LL*(a.r+b.r)*(a.r+b.r);
}

void init_grid(int64_t size) {
	grid.clear();
	grid_size = size;
	for (int64_t i = 0; i < n; i++) {
		if (eliminator[circles[i].idx]) {
			continue;
		}

		grid[circles[i].x/size][circles[i].y/size].emplace_back(circles[i]);
	}
}

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

	std::cin >> n;
	for (int64_t i = 0, x, y, r; i < n; i++) {
		std::cin >> x >> y >> r;
		circles.emplace_back(x,y,r,i);
	}

	std::sort(circles.begin(),circles.end(),[](const Circle& a, const Circle& b) {
		return a.r > b.r;
	});

	eliminator.assign(n, 0);
	init_grid(4LL*circles[0].r*circles[0].r);
	for (const auto& [x, y, r, idx] : circles) {
		if (4LL*r*r < grid_size/2) {
			init_grid(4LL*r*r);
		}
		if (eliminator[idx]) {
			continue;
		}

		eliminator[idx] = idx+1;

		//std::cout << idx << " " << grid_size << "\n";

		int64_t grid_x = x / grid_size;
		int64_t grid_y = y / grid_size;

		for (auto add_x : {-2, -1, 0, 1, 2}) {
			for (auto add_y : {-2, -1, 0, 1, 2}) {
				for (const auto& j : grid[grid_x+add_x][grid_y+add_y]) {
					if (eliminator[j.idx]) {
						continue;
					}

					if (int64_tersect(Circle(x,y,r,idx), j)) {
						eliminator[j.idx] = idx+1;
					}
				}
			}
		}
	}

	for (int64_t i = 0; i < n; i++) {
		std::cout << eliminator[i] << " ";
	}
	std::cout << "\n";
}

컴파일 시 표준 에러 (stderr) 메시지

circle_selection.cpp:23:1: error: 'int64_t64_t' does not name a type; did you mean 'int_fast64_t'?
   23 | int64_t64_t grid_size;
      | ^~~~~~~~~~~
      | int_fast64_t
circle_selection.cpp:26:8: error: 'int64_t64_t' does not name a type; did you mean 'int_fast64_t'?
   26 | inline int64_t64_t euclid_dist(const Circle& a, const Circle& b) {
      |        ^~~~~~~~~~~
      |        int_fast64_t
circle_selection.cpp: In function 'bool int64_tersect(const Circle&, const Circle&)':
circle_selection.cpp:37:16: error: 'euclid_dist' was not declared in this scope
   37 |         return euclid_dist(a,b) <= 1LL*(a.r+b.r)*(a.r+b.r);
      |                ^~~~~~~~~~~
circle_selection.cpp: In function 'void init_grid(int64_t)':
circle_selection.cpp:42:9: error: 'grid_size' was not declared in this scope
   42 |         grid_size = size;
      |         ^~~~~~~~~
circle_selection.cpp: In function 'int main()':
circle_selection.cpp:70:31: error: 'grid_size' was not declared in this scope
   70 |                 if (4LL*r*r < grid_size/2) {
      |                               ^~~~~~~~~
circle_selection.cpp:81:38: error: 'grid_size' was not declared in this scope
   81 |                 int64_t grid_x = x / grid_size;
      |                                      ^~~~~~~~~