Submission #555854

#	Time	Username	Problem	Language	Result	Execution time	Memory
555854		Magi	Park (BOI16_park)	C++14	0 / 100	5 ms	468 KiB

park

#include <iostream>
#include <vector>
#define ll long long

using namespace std;

const int NMAX = 2e3;
int n, m, w, h, viz[NMAX+10];
vector <int> nod[NMAX+10];

struct circle{
	int x, y, r;
	bool intersectEdge(int t){
		if(!t)
			return y - r < 0;
		if(t == 1)
			return x + r > w;
		if(t == 2)
			return y + r > h;
		return x - r < 0;
	}
	bool intersectCircle(const circle& other){
		return (ll)(x - other.x) * (ll)(x - other.x) + (ll)(y - other.y) * (ll)(y - other.y) < (ll)(r + other.r) * (ll)(r + other.r);
	}
}v[NMAX+10];

void dfs(int x, int col){
	viz[x] = col;
	for(auto u : nod[x])
		if(!viz[u])
			dfs(u, col);
}

int main(){

	ios_base::sync_with_stdio(false);
	cin.tie(0);

	cin >> n >> m >> w >> h;
	for(int i=1; i<=n; i++)
		cin >> v[i].x >> v[i].y >> v[i].r;

	//solving subtask 1 (only 1 query)
	int r1, e;
	cin >> r1 >> e;
	for(int i=1; i<=n; i++)
		v[i].r += r1;

	for(int i=1; i<=n; i++){
		//check collision with edges
		for(int t=0; t<4; t++)
			if(v[i].intersectEdge(t)){
				nod[i+3].push_back(t);
				nod[t].push_back(i+3);
			}
		//check collision with other circles
		for(int j=i+1; j<=n; j++)
			if(v[i].intersectCircle(v[j])){
				nod[i+3].push_back(j+3);
				nod[j+3].push_back(i+3);
			}
	}

	int col = 0;
	for(int t=0; t<4; t++){
		if(viz[t])
			continue;
		dfs(t, ++col);
	}

	e--;
	bool ans[4];
	for(int t=0; t<4; t++)
		ans[t] = false;
	ans[e] = true;

	if(viz[e] != viz[(e+3)%4]){
		//adjacent counterclockwise
		if(viz[e] != viz[(e+2)%4] && viz[e] != viz[(e+1)%4])
			ans[(e+1)%4] = true;
		//opposite
		if(viz[e] != viz[(e+2)%4] && viz[(e+1)%4] != viz[(e+3)%4] && viz[(e+1)%4] != viz[(e+2)%4])
			ans[(e+2)%4] = true;
		//adjacent clockwise
		if(viz[(e+1)%4] != viz[(e+3)%4] && viz[(e+2)%4] != viz[(e+3)%4])
			ans[(e+3)%4] = true;
	}

	for(int t=0; t<4; t++)
		if(ans[t])
			cout << t + 1;
	cout << '\n';
	

	return 0;
}

• Subtask 1: 0 / 27
• Subtask 2: 0 / 31
• Subtask 3: 0 / 42