fork download
copy 
  1. #include <bits/stdc++.h>
  2. #include <iostream>
  3. #include <string>
  4. #include <cmath>
  5. #include <vector>
  6. #include <map>
  7. #include <limits>
  8. #include <queue>
  9. #include <stack>
  10. #include <fstream>
  11. #define maxN 10002
  12. using namespace std;
  13. int n,m; // n la so sensor , m la so target
  14. int cnt=0;
  15. double rC ; // ban kinh truyen tin ;
  16. double rS ; // ban kinh bao phu
  17. int used[maxN];
  18. int a[2001][2001];
  19. double x[2001],y[2001];
  20. int d[maxN], par[maxN];
  21. bool visit[maxN];
  22. void input()   // nhap vao cac toa do cua sensor va base voi qui uoc (x[0],y[0]) la toa do do cua base;
  23.     {   
  24.         cin >> n >> m  >> rC >> rS ;
  25.         for(int i = 0 ; i <= n ; i++)  // nhap vap vi tri cua base station ( x[0],y[0]) va toa do cua n sensor;
  26.                 cin >> x[i] >> y[i];
  27.         for(int i = n+1 ; i<= n+m ;i++) // nhap vao vi tri cua m target ;
  28.                 cin >> x[i] >> y[i];
  29.     }
  30. double distance (double x,double y,double z, double t )  // tinh khoang cach
  31.     {
  32.         double seg = sqrt((x-z)*(x-z)+(y-t)*(y-t));
  33.         return seg;
  34.     }
  35. void graphModel() // dua ve mo hinh do thi
  36.     {
  37.         for(int i = 0 ; i <= n ; i++)   // noi cac canh giua cac sensor va base station;
  38.             for( int j = 0 ; j <= n ;j ++)
  39.                 {
  40.                     if(i==j)
  41.                         a[i][j]=0;
  42.                     else
  43.                         {
  44.                             if(distance(x[i],y[i],x[j],y[j]) <= rC )
  45.                                 a[i][j]=1;
  46.                                 a[j][i]=1;
  47.                         }                        
  48.                 }
  49.         for(int i = n+1 ; i <= n+m ; i++) // noi canh giua target va sensor neu khoang cach  <= rS
  50.             for(int j = 1 ;j <=n ; j++)
  51.                 if(distance(x[i],y[i],x[j],y[j]) <= rS){
  52.                     a[i][j]=1;
  53.                     a[j][i]=1;
  54.                 }
  55.     }
  56. void fix(){
  57.     for(int i = 1 ; i <=m+ n; i++){   // ham cap nhat lai ket qua sau khi de qui
  58.         used[i]=0;
  59.     }
  60. }
  61. void bfs(int s)  // xet s la dinh dang xet , o bai toan nay ta se bfs tu base station
  62.  {
  63.     fill_n(d, n + 1, 0);
  64.     fill_n(par, n + 1, -1);
  65.     fill_n(visit, n + 1, false); // ham kiem tra la da tham dinh hay chua 
  66.     queue <int> q;
  67.     q.push(s);
  68.     visit[s] = true;
  69.     while (!q.empty()) 
  70.     {
  71.         int u = q.front();
  72.         q.pop();
  73.         for (int v = 0 ;  v <= n ; v++) 
  74.         {
  75.             if(a[v][u]==1 && used [v]==0)
  76.                 if (!visit[v]) 
  77.                 {
  78.                     d[v]     = d[u] + 1; // cap nhat do dai duong di ngan nhat
  79.                     par[v]   = u; // truy vet duong di
  80.                     visit[v] = true;
  81.                     q.push(v);
  82.                 }
  83.         }
  84.     }
  85. }
  86. void delete_vertex(int s) // xoa mot dinh
  87.     {
  88.         for(int i = 0 ; i <= m+n; i++)
  89.             {
  90.                 a[s][i]=0;
  91.                 a[i][s]=0;
  92.             }
  93.     }
  94. void delete_edge(int s, int t) // xoa canh s->t
  95.     {
  96.         a[s][t]=0;
  97.         a[t][s]=0;
  98.     }
  99. void add_edge(int s,int t)
  100.     {
  101.         a[s][t]=1;
  102.         a[t][s]=1;
  103.     }
  104. int checkPath(int source){
  105.     int sea=-1;
  106.     int abc=INT_MAX;
  107.     for(int i =1 ; i <= n; i++){
  108.         if(a[source][i] == 1 && d[i] != 0 && used[i]==0){
  109.             if(abc> d[i]){
  110.                 abc=d[i];
  111.                 sea=i;
  112.             }
  113.         }
  114.     }
  115.     return sea;
  116. }
  117. int naive(int source) // ham phu. tinh so duong di phan biet tu source den sink ( source o day chinh la target )
  118.     {
  119.             bfs(0);  // bfs tu di?nh root la 0 (chinh la base station)
  120.             int temp=checkPath(source);
  121.             if(temp==-1){
  122.                 return 0;
  123.             }
  124.             else{
  125.                 while(temp!=0){
  126.                     used[temp]=1;   // danh dau nhung dinh bi bo
  127.                     temp=par[temp];
  128.                 }
  129.                 return naive(source)+1;
  130.         }                   
  131.     }   
  132. int main()
  133.     {   
  134.  
  135.         input();
  136.         graphModel();
  137.         cnt=0;
  138.         cout << "Hello" << endl;
  139.         int example ;
  140.         cin >> example;
  141.  
  142.         /*cout << "Ket qua cua bien search trong ham MeDisPath(3) la : ";
  143.         MebDisjPath(3); */
  144.         cout << naive(3) << endl;
  145.         cout << used[1] << endl;
  146.         fix();
  147.         cout << naive(4) << endl;
  148.         fix();
  149.         //cout << "Ket qua cua ham naive(3) va naive(4) la: \n" << l <<" \n " << r << endl;
  150.         // naive(3);
  151.         //cout << "So duong di phan biet tu target " << example <<" toi base station la: " << MebDisjPath(example)  << endl;
  152.  
  153.     }
Success #stdin #stdout 0s 5308KB
comments (?)
stdin
copy 
2
2
1
1
0 0
0.1 0.1
0.2 0.2
0.12 0.12
0.13 0.13
3
stdout
copy 
Hello
2
1
2
https://ideone.com/ML7PkE
language:
C++ (gcc 8.3)
created:
12 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!