Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- typedef unsigned long long ull;
- typedef vector<int> vi;
- typedef vector<ll> vll;
- int inf_int=2e9;
- ll inf_ll=2e18;
- typedef pair<int,int> pii;
- #define pb push_back
- const double pi=3.1415926535898;
- #define dout if(debug) cout
- #define fi first
- #define se second
- #define sp setprecision
- #define sz size()
- #define x1 gfgs
- #define y1 asd
- bool debug=0;
- int x[1010],y[1010],r[1010];
- bool used[1010],clo[1010];
- vector<int> g[1010];
- int rat[1010][10010];
- ll nod(ll x,ll y)
- {
- if(y==0)
- {
- return x;
- }
- return nod(y,x%y);
- }
- void solve()
- {
- int n;
- cin >> n;
- for(int i=0;i<n;i++)
- {
- cin >> x[i]>>y[i]>>r[i];
- }
- for(int i=0;i<n;i++)
- {
- for(int e=i+1;e<n;e++)
- {
- if((x[i]-x[e])*(x[i]-x[e])+(y[i]-y[e])*(y[i]-y[e])==(r[i]+r[e])*(r[i]+r[e]))
- {
- g[i].pb(e);
- g[e].pb(i);
- }
- }
- }
- vector<int> pr;
- pr.pb(2);
- for(int i=3;i<=1e4;i++)
- {
- bool k=1;
- for(int e=0;pr[e]*pr[e]<=i;e++)
- {
- if(i%pr[e]==0)
- {
- k=0;
- break;
- }
- }
- if(k)
- {
- pr.pb(i);
- }
- }
- queue<int> q;
- q.push(0);
- used[0]=1;
- clo[0]=1;
- rat[0][1]=1;
- while(!q.empty())
- {
- int v=q.front();
- q.pop();
- for(int i=0;i<g[v].sz;i++)
- {
- int to=g[v][i];
- if(used[to])
- {
- if(clo[to]==clo[v])
- {
- cout << -1;
- return;
- }
- }
- else
- {
- clo[to]=!clo[v];
- used[to]=1;
- q.push(to);
- ll x=r[v],y=r[to];
- ll nd=nod(x,y);
- x=x/nd;
- y=y/nd;
- for(int e=0;e<=10000;e++)
- {
- rat[to][e]=rat[v][e];
- }
- for(int e=0;pr[e]*pr[e]<=x;e++)
- {
- while(x%pr[e]==0)
- {
- rat[to][pr[e]]++;
- x=x/pr[e];
- }
- }
- for(int e=0;pr[e]*pr[e]<=y;e++)
- {
- while(y%pr[e]==0)
- {
- rat[to][pr[e]]--;
- y=y/pr[e];
- }
- }
- rat[to][x]++;
- rat[to][y]--;
- }
- }
- }
- if(!used[n-1])
- {
- cout << 0;
- return;
- }
- ll ans1=1,ans2=1;
- for(int i=0;i<=1e4;i++)
- {
- if(rat[0][i]>=rat[n-1][i])
- {
- rat[0][i]=rat[0][i]-rat[n-1][i];
- rat[n-1][i]=0;
- }
- else
- {
- rat[n-1][i]=abs(rat[0][i]-rat[n-1][i]);
- rat[0][i]=0;
- }
- while(rat[0][i])
- {
- ans1=ans1*i;
- rat[0][i]--;
- }
- while(rat[n-1][i])
- {
- ans2=ans2*i;
- rat[n-1][i]--;
- }
- }
- if(clo[0]==clo[n-1])
- {
- cout << ans1<<" "<<ans2;
- }
- else
- {
- cout << ans1<<" "<<-ans2;
- }
- }
- #define FILE "humble"
- int main()
- {
- // freopen("input.txt","r",stdin);
- // freopen("output.txt","w",stdout);
- // freopen(FILE".in","r",stdin);
- // freopen(FILE".out","w",stdout);
- if(!debug)
- {
- ios_base::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- }
- int t=1;
- while(t--)
- solve();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement