caidistra
quoc14
c_cpp
a month ago
2.2 kB
3
Indexable
Never
caidat
#include <iostream> using namespace std; int n; const int oo = 99999999; double abss(double n) { if (n < 0) return -n; else return n; } double canbac2(double left, double right, int n) { double mid = (left + right)/2; //cout << mid <<" " << mid*mid << endl; if (abss(mid*mid - n) < 0.0000001) return mid; if (mid*mid < n) return canbac2(mid,right, n); else return canbac2(left, mid, n); } struct point{ int x; int y; int r; }; point a[1002]; int map[1003][1002]; int nhayngan[1000]; int dem[1000]; int kt[1000]; int chiphi[1002]; int khoangcach(point aa, point bb) { int h1 = abss(aa.x - bb.x); int h2 = abss(aa.y - bb.y); int bp = h1*h1 + h2*h2; double kc = canbac2(0, bp, bp); kc = kc - aa.r - bb.r; if (kc <= 40) return 1; else if (kc > 40 && kc <= 90) return 500; else return 0; } void dijkstra() { for (int i = 1; i<=n; i++) { chiphi[i] = oo; kt[i] = 0; dem[i] = 0; nhayngan[i] = 0; } chiphi[1] = 0; while (true) { int minn = oo; int pos = -1; for (int i = 1; i<=n; i++) if (kt[i] == 0 && chiphi[i] < minn) { minn = chiphi[i]; pos = i; } if (pos == -1) break; kt[pos] = 1; for (int i = 1; i<= n; i++) if (kt[i] == 0 && map[pos][i] != 0 && chiphi[i] > chiphi[pos] + map[pos][i]) { chiphi[i] = chiphi[pos] + map[pos][i]; if (map[pos][i] == 1) nhayngan[i] = nhayngan[pos] + 1; else nhayngan[i] = nhayngan[pos]; dem[i] = dem[pos] + 1; } } } int main() { //freopen("input.txt","r",stdin); int ntc; cin >> ntc; for (int tc=1; tc<=ntc; tc++) { int tmp; cin >> n; for (int i = 1; i<=n; i++) cin >> a[i].x >> a[i].y >> a[i].r; for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) if (i!=j) { map[i][j] = khoangcach(a[i], a[j]); } /*for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) cout << map[i][j] << " "; cout << endl; }*/ dijkstra(); if (chiphi[n] == oo) cout << -1 << endl; else cout << dem[n] - nhayngan[n] << " "<< nhayngan[n] << endl; } return 0; }
Leave a Comment