Submission #59989

#	Time	Username	Problem	Language	Result	Execution time	Memory
59989		Eae02	Circle selection (APIO18_circle_selection)	C++14	19 / 100	3069 ms	21544 KiB

circle_selection

#include <bits/stdc++.h>
#define ALL(x) x.begin(),x.end()

struct Circle
{
	int64_t x;
	int64_t y;
	int64_t r;
	int64_t i;
	int64_t elimBy;
	
	int64_t minX() const { return x - r; }
	int64_t maxX() const { return x + r; }
	int64_t minY() const { return y - r; }
	int64_t maxY() const { return y + r; }
	
	bool intersects(const Circle& other) const
	{
		int64_t dx = x - other.x;
		int64_t dy = y - other.y;
		int64_t rSum = r + other.r;
		return dx * dx + dy * dy <= rSum * rSum;
	}
	
	bool contains(int64_t x, int64_t y) const
	{
		int64_t dx = x - this->x;
		int64_t dy = y - this->y;
		return dx * dx + dy * dy <= r * r;
	}
};

Circle* outerCircle;

struct OctNode
{
	int64_t minX;
	int64_t minY;
	int64_t maxX;
	int64_t maxY;
	std::vector<Circle*> circles;
	OctNode* children[4];
	
	bool intersects(const Circle& c)
	{
		if (c.contains(minX, minY) || c.contains(minX, maxY - 1) || c.contains(maxX - 1, minY) || c.contains(maxX - 1, maxY - 1))
			return true;
		if (c.x >= minX && c.x < maxX && c.y >= minY && c.y < maxY)
			return true;
		return false;
	}
	
	bool contains(int64_t x, int64_t y, int64_t r)
	{
		return x - r >= minX && x + r < maxX && y - r >= minY && y + r < maxY;
	}
	
	void mark()
	{
		for (int i = 0; i < 4; i++)
		{
			if (children[i] && children[i]->intersects(*outerCircle))
				children[i]->mark();
		}
		
		for (long i = circles.size() - 1; i >= 0; i--)
		{
			if (circles[i]->elimBy == -1 && circles[i]->intersects(*outerCircle))
			{
				circles[i]->elimBy = outerCircle->i;
				circles[i] = circles.back();
				circles.pop_back();
			}
		}
	}
};

void genOctree(OctNode* node)
{
	int64_t halfSX = (node->maxX - node->minX) / 2;
	int64_t halfSY = (node->maxY - node->minY) / 2;
	int64_t midX = node->minX + halfSX;
	int64_t midY = node->minY + halfSY;
	
	bool subdivide = false;
	for (Circle* circle : node->circles)
	{
		if (circle->maxX() < midX || circle->minX() > midX || circle->maxY() > midY || circle->minY() < midY)
		{
			subdivide = true;
			break;
		}
	}
	
	if (!subdivide)
		return;
	
	for (int i = 0; i < 4; i++)
	{
		OctNode* child = new OctNode;
		
		child->minX = (i % 2) ? midX : node->minX;
		child->maxX = (i % 2) ? node->maxX : midX;
		child->minY = (i / 2) ? midY : node->minY;
		child->maxY = (i / 2) ? node->maxY : midY;
		
		child->circles.reserve(node->circles.size());
		
		for (int j = node->circles.size() - 1; j >= 0; j--)
		{
			if (node->intersects(*node->circles[j]))
			{
				child->circles.push_back(node->circles[j]);
				node->circles[j] = node->circles.back();
				node->circles.pop_back();
			}
		}
		
		if (child->circles.empty())
		{
			delete child;
			node->children[i] = nullptr;
		}
		else
			node->children[i] = child;
	}
}

int main()
{
	int num;
	std::cin >> num;
	std::vector<Circle> circles(num);
	std::vector<Circle*> cByMin(num);
	std::vector<Circle*> cByMax(num);
	
	bool allZeroY = true;
	int64_t sameRad = -1;
	
	for (int i = 0; i < num; i++)
	{
		std::cin >> circles[i].x;
		std::cin >> circles[i].y;
		std::cin >> circles[i].r;
		circles[i].i = i;
		circles[i].elimBy = -1;
		cByMin[i] = &circles[i];
		cByMax[i] = &circles[i];
		
		if (i == 0)
			sameRad = circles[i].r;
		else if (sameRad != circles[i].r)
			sameRad = -1;
		
		if (circles[i].y != 0)
			allZeroY = false;
	}
	
	if (sameRad == -1)
	{
		std::sort(ALL(circles), [&] (const Circle& a, const Circle& b)
		{
			if (a.r == b.r)
				return a.i < b.i;
			return a.r > b.r;
		});
	}
	
	if (allZeroY)
	{
		std::sort(ALL(cByMin), [&] (const Circle* a, const Circle* b)
		{
			return a->minX() < b->minX();
		});
		
		std::sort(ALL(cByMax), [&] (const Circle* a, const Circle* b)
		{
			return a->maxX() < b->maxX();
		});
		
		for (Circle& outer : circles)
		{
			if (outer.elimBy != -1)
				continue;
			outer.elimBy = outer.i;
			
			auto minB = std::lower_bound(ALL(cByMin), outer.minX(), [&] (Circle* c, int64_t pos) { return c->minX() < pos; });
			auto minE = std::upper_bound(ALL(cByMin), outer.maxX(), [&] (int64_t pos, Circle* c) { return pos < c->minX(); });
			
			auto maxB = std::lower_bound(ALL(cByMax), outer.minX(), [&] (Circle* c, int64_t pos) { return c->maxX() < pos; });
			auto maxE = std::upper_bound(ALL(cByMax), outer.maxX(), [&] (int64_t pos, Circle* c) { return pos <= c->maxX(); });
			
			std::for_each(minB, minE, [&] (Circle* c)
			{
				if (c->elimBy == -1)
					c->elimBy = outer.i;
			});
			std::for_each(maxB, maxE, [&] (Circle* c)
			{
				if (c->elimBy == -1)
					c->elimBy = outer.i;
			});
		}
	}
	else if (num <= 5000)
	{
		for (Circle& outer : circles)
		{
			if (outer.elimBy != -1)
				continue;
			outer.elimBy = outer.i;
			for (Circle& inner : circles)
			{
				if (inner.elimBy == -1 && inner.intersects(outer))
					inner.elimBy = outer.i;
			}
		}
	}
	else
	{
		int64_t minX;
		int64_t minY;
		int64_t maxX;
		int64_t maxY;
		
		OctNode root;
		root.circles.reserve(circles.size());
		root.minX = INT64_MAX;
		root.minY = INT64_MAX;
		root.maxX = INT64_MIN;
		root.maxY = INT64_MIN;
		
		for (Circle& circle : circles)
		{
			root.circles.push_back(&circle);
			root.minX = std::min(root.minX, circle.minX());
			root.maxX = std::min(root.maxX, circle.maxX());
			root.minY = std::min(root.minY, circle.minY());
			root.maxY = std::min(root.maxY, circle.maxY());
		}
		root.maxX++;
		root.maxY++;
		
		genOctree(&root);
		
		for (Circle& circle : circles)
		{
			if (circle.elimBy == -1)
			{
				circle.elimBy = circle.i;
				outerCircle = &circle;
				root.mark();
			}
		}
	}
	
	std::vector<int64_t> result(num);
	for (int i = 0; i < num; i++)
		result[circles[i].i] = circles[i].elimBy + 1;
	for (int i = 0; i < num; i++)
		std::cout << result[i] << " ";
	std::cout << std::endl;
}

Compilation message (stderr)

circle_selection.cpp: In function 'int main()':
circle_selection.cpp:221:11: warning: unused variable 'minX' [-Wunused-variable]
   int64_t minX;
           ^~~~
circle_selection.cpp:222:11: warning: unused variable 'minY' [-Wunused-variable]
   int64_t minY;
           ^~~~
circle_selection.cpp:223:11: warning: unused variable 'maxX' [-Wunused-variable]
   int64_t maxX;
           ^~~~
circle_selection.cpp:224:11: warning: unused variable 'maxY' [-Wunused-variable]
   int64_t maxY;
           ^~~~

• Subtask 1: 7 / 7
• Subtask 2: 12 / 12
• Subtask 3: 0 / 15
• Subtask 4: 0 / 23
• Subtask 5: 0 / 30
• Subtask 6: 0 / 13