记录编号	404667	评测结果	AAAAAAAAAA
题目名称	[USACO Mar08] 混乱的齿轮	最终得分	100
用户昵称	HeHe	是否通过	通过
代码语言	C++	运行时间	0.007 s
提交时间	2017-05-14 11:05:07	内存使用	0.32 MiB

#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
#include <vector>
using namespace std;

const int MAXN = 2e3;

inline int in(void){ 
	char tmp = getchar();
	int res = 0, f = 1;
	while(!isdigit(tmp) && tmp != '-')tmp = getchar();
	if(tmp == '-')f = -1, tmp = getchar();
	while(isdigit(tmp))
		res = (res + (res << 2) << 1) + (tmp ^ 48),
		tmp = getchar();
	return res * f;
}

struct DATA{ 
	int x, y;
	int r;

	DATA(){ 
		x = 0, y = 0, r = 0;
	}

	DATA(int c, int b, int a){ 
		x = a, y = b, r = c;
	}
};

struct EDGE{ 
	int to, ne;

	EDGE(){ 
		to = 0, ne = -1;
	}

	EDGE(int a, int b){ 
		to = a, ne = b;
	}
};

inline bool check(const DATA& a, const DATA& b);
inline void add_edge(int fr, int to);
inline int bfs(int s);

vector<DATA> rollers;
vector<EDGE> edge;
int head[MAXN];
int N, ans, sta;

int main(){ 
#ifndef LOCAL
	freopen("rollers.in", "r", stdin);
	freopen("rollers.out", "w", stdout);
#else
	freopen("test.in", "r", stdin);
#endif
	memset(head, 0xff, sizeof(head));

	N = in();

	for(int i = 0, a, b; i < N; ++i){ 
		rollers.push_back(DATA(in(), b = in(), a = in()));
		if(!a && !b)sta = i;
	}
	
	for(int i = 0; i < N; ++i){ 
		for(int j = i + 1; j < N; ++j){ 
			if(check(rollers[i], rollers[j]))add_edge(i, j);
		}
	}

	ans = bfs(sta);

	printf("%d %d", rollers[ans].x, rollers[ans].y);

	return 0;

}

inline bool check(const DATA& a, const DATA& b){ 
	int dx = a.x - b.x;
	int dy = a.y - b.y;
	int dr = a.r + b.r;
	return dx * dx + dy * dy == dr * dr;
}

inline void add_edge(int fr, int to){ 
	edge.push_back(EDGE(to, head[fr])), head[fr] = edge.size() - 1;
	edge.push_back(EDGE(fr, head[to])), head[to] = edge.size() - 1;
	return ;
}

inline int bfs(int s){ 
	static queue<int> que;
	static bool vis[MAXN];
	static int u, v, res;

	while(!que.empty()) que.pop();
	memset(vis, 0x00, sizeof(vis));

	que.push(s);
	vis[s] = true;

	while(!que.empty()){ 
		u = que.front();
		que.pop();
		res = u;

		for(int i = head[u]; ~i; i = edge[i].ne){ 
			if(vis[v = edge[i].to]) continue;
			que.push(v);
			vis[v] = true;
		}
	}

	return res;
}