Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <stdio.h>
- #include <vector>
- #include <string>
- #include <math.h>
- #include <algorithm>
- #include <map>
- #include <set>
- #include <functional>
- #include <unordered_map>
- #include <queue>
- #define sz(x) ((int64)x.size())
- #define all(x) (x).begin(), (x).end()
- #define pb(x) push_back(x)
- #define mp(x, y) make_pair(x, y)
- typedef long long int64;
- using namespace std;
- int gcd(int a, int b) {
- return b ? gcd(b, a % b) : a;
- }
- int sqr(int x) {
- return x * x;
- }
- int main() {
- int n;
- cin >> n;
- vector<int> x(n), y(n), r(n);
- for (int i = 0; i < n; ++i) cin >> x[i] >> y[i] >> r[i];
- vector<vector<int> > g(n);
- for (int i = 0; i < n; ++i) {
- for (int j = 0; j < n; ++j) {
- if (i == j) continue;
- if (sqr(x[j] - x[i]) + sqr(y[j] - y[i]) == sqr(r[i] + r[j])) {
- g[i].pb(j);
- }
- }
- }
- queue<int> q;
- q.push(0);
- vector<int> part(n, -1);
- part[0] = 0;
- while (!q.empty()) {
- int v = q.front();
- q.pop();
- for (int j = 0; j < sz(g[v]); ++j) {
- int to = g[v][j];
- if (part[to] == -1) {
- part[to] = 1 - part[v];
- q.push(to);
- } else {
- if (part[v] == part[to]) {
- cout << "-1" << endl;
- return 0;
- }
- }
- }
- }
- if (part[n - 1] == -1) {
- cout << "0" << endl;
- return 0;
- }
- int d = gcd(r[0], r[n - 1]);
- cout << r[n - 1] / d << " ";
- if (part[n - 1] == 1) cout << "-";
- cout << r[0] / d << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment