Guest User

Untitled

a guest
Feb 14th, 2016
230
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.67 KB | None | 0 0
  1. #include <iostream>
  2. #include <stdio.h>
  3. #include <vector>
  4. #include <string>
  5. #include <math.h>
  6. #include <algorithm>
  7. #include <map>
  8. #include <set>
  9. #include <functional>
  10. #include <unordered_map>
  11. #include <queue>
  12.  
  13. #define sz(x) ((int64)x.size())
  14. #define all(x) (x).begin(), (x).end()
  15. #define pb(x) push_back(x)
  16. #define mp(x, y) make_pair(x, y)
  17.  
  18. typedef long long int64;
  19.  
  20. using namespace std;
  21.  
  22. int gcd(int a, int b) {
  23.     return b ? gcd(b, a % b) : a;
  24. }
  25.  
  26. int sqr(int x) {
  27.     return x * x;
  28. }
  29.  
  30. int main() {
  31.     int n;
  32.     cin >> n;
  33.     vector<int> x(n), y(n), r(n);
  34.     for (int i = 0; i < n; ++i) cin >> x[i] >> y[i] >> r[i];
  35.     vector<vector<int> > g(n);
  36.     for (int i = 0; i < n; ++i) {
  37.         for (int j = 0; j < n; ++j) {
  38.             if (i == j) continue;
  39.             if (sqr(x[j] - x[i]) + sqr(y[j] - y[i]) == sqr(r[i] + r[j])) {
  40.                 g[i].pb(j);
  41.             }
  42.         }
  43.     }
  44.     queue<int> q;
  45.     q.push(0);
  46.     vector<int> part(n, -1);
  47.     part[0] = 0;
  48.     while (!q.empty()) {
  49.         int v = q.front();
  50.         q.pop();
  51.         for (int j = 0; j < sz(g[v]); ++j) {
  52.             int to = g[v][j];
  53.             if (part[to] == -1) {
  54.                 part[to] = 1 - part[v];
  55.                 q.push(to);
  56.             } else {
  57.                 if (part[v] == part[to]) {
  58.                     cout << "-1" << endl;
  59.                     return 0;
  60.                 }
  61.             }
  62.         }
  63.     }
  64.     if (part[n - 1] == -1) {
  65.         cout << "0" << endl;
  66.         return 0;
  67.     }
  68.  
  69.     int d = gcd(r[0], r[n - 1]);
  70.     cout << r[n - 1] / d << " ";
  71.     if (part[n - 1] == 1) cout << "-";
  72.     cout << r[0] / d << endl;
  73.     return 0;
  74. }
Advertisement
Add Comment
Please, Sign In to add comment