Submission #257186

#	Time	Username	Problem	Language	Result	Execution time	Memory
257186		maximath_1	Park (BOI16_park)	C++11	100 / 100	1141 ms	66464 KiB

park

#include <iostream>
#include <algorithm>
#include <math.h>
#include <iomanip>
#include <vector>
using namespace std;

#define ld long double
#define ll long long

int n, m;
ll w, h;
struct circle{ll x, y, r;} v[2005];
int par[2020];
vector<pair<pair<int, int>, ld> > edge;

ld dist_to_wall(circle a, int b){
	if(b == 0) return a.y - a.r;
	if(b == 1) return w - a.x - a.r;
	if(b == 2) return h - a.y - a.r;
	if(b == 3) return a.x - a.r;
	return -1.0;
}
ld dist_pt(pair<ll, ll> a, pair<ll, ll> b){
	ll xx = b.first - a.first, yy = b.second - a.second;
	ll sq2 = xx * 1ll * xx + yy * 1ll * yy;
	return (ld)sqrtl(sq2);
}
ld dist_between_circle(circle a, circle b){
	ld dst_rad = dist_pt({a.x, a.y}, {b.x, b.y});
	dst_rad -= (ld)a.r + (ld)b.r;
	return dst_rad;
}

bool cmp(pair<pair<int, int>, ld> a, pair<pair<int, int>, ld> b){
	return a.second < b.second;
}

int find(int x){
	if(x != par[x]) par[x] = find(par[x]);
	return par[x];
}

ld cst[4][4], ans[4][4];

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

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

	for(int i = 0; i < n; i ++){
		for(int j = i + 1; j < n; j ++)
			edge.push_back({{i, j}, dist_between_circle(v[i], v[j])});
		for(int j = n; j < n + 4; j ++)
			edge.push_back({{i, j}, dist_to_wall(v[i], j - n)});
	}

	sort(edge.begin(), edge.end(), cmp);

	for(int i = 0; i < n + 4; i ++) par[i] = i;
	for(int i = 0; i < 4; i ++) for(int j = 0; j < 4; j ++) cst[i][j] = -1.0;

	for(auto i : edge){
		int u = i.first.first, v = i.first.second;
		ld w = i.second;

		int fu = find(u), fv = find(v);
		if(fu != fv) par[fu] = fv;

		for(int a = n; a < n + 4; a ++) for(int b = a + 1; b < n + 4; b ++){ //check walls connected (as if becomes a room)
			if(find(a) == find(b) && cst[a - n][b - n] == -1.0)
				cst[a - n][b - n] = w;
		}
	}

	ans[0][0] = ans[1][1] = ans[2][2] = ans[3][3] = 2e9 + 69;
	ans[0][1] = ans[1][0] = min(cst[0][1], min(cst[0][2], cst[0][3]));
	ans[0][2] = ans[2][0] = min(min(cst[0][3], cst[1][2]), min(cst[0][2], cst[1][3]));
	ans[0][3] = ans[3][0] = min(cst[0][3], min(cst[1][3], cst[2][3]));
	ans[1][2] = ans[2][1] = min(cst[0][1], min(cst[1][3], cst[1][2]));
	ans[1][3] = ans[3][1] = min(min(cst[0][1], cst[2][3]), min(cst[0][2], cst[1][3]));
	ans[2][3] = ans[3][2] = min(cst[2][3], min(cst[1][2], cst[0][2]));

	for(int r, st, i = 0; i < m; i ++){
		cin >> r >> st;
		st --;
		ld dia = 2.0L * r;
		for(int ed = 0; ed < 4; ed ++)
			if(dia <= ans[st][ed]) cout << ed + 1;
		cout << endl;
	}

	return 0;
}

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