Advertisement
Guest User

Untitled

a guest
Jan 19th, 2017
73
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.07 KB | None | 0 0
  1. #include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
  2. #include <CGAL/Delaunay_triangulation_2.h>
  3.  
  4. typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
  5. typedef CGAL::Delaunay_triangulation_2<K>  Triangulation;
  6. typedef Triangulation::Edge_iterator  Edge_iterator;
  7. typedef Triangulation::Finite_faces_iterator FI;
  8. typedef K::Point_2 P;
  9. typedef K::Segment_2 S;
  10. typedef Triangulation::Face_handle FH;
  11.  
  12. using namespace std;
  13. using namespace CGAL;
  14.  
  15. bool dfs(FH& start_face, map<FH, int>& visited, Triangulation& t, double d, int round){
  16.     visited[start_face] = round;
  17.     if(t.is_infinite(start_face)){
  18.         //cout << "infinite" << endl;
  19.         return true;
  20.     }
  21.     //for all thre neighbouring faces
  22.     for(int i=0; i<3; ++i){
  23.         FH neighbor = start_face->neighbor(i);
  24.         if(visited[neighbor] != round){
  25.             //Triangulation::Segment
  26.             S seg = t.segment(start_face, i);
  27.             double distance = CGAL::to_double(seg.squared_length());
  28.             //cout << "distance " << distance << " 4d " << 4*d << endl;
  29.             if(distance >= 4*d){
  30.                 if(t.is_infinite(neighbor)) return true;
  31.  
  32.                 if(dfs(neighbor, visited, t, d, round))
  33.                     return true;
  34.             }
  35.         }
  36.     }
  37.     return false;
  38. }
  39.  
  40.  
  41. void do_testcases(int n){
  42.     // read in infected patients
  43.     vector<P> infected(n);
  44.     for (int i=0; i<n; ++i) {
  45.         cin >> infected[i];
  46.     }
  47.     // construct triangulation
  48.     Triangulation t;
  49.     t.insert(infected.begin(), infected.end());
  50.    
  51.     int m; cin >> m;
  52.  
  53.     map<FH, int> visited;
  54.     for (FI f = t.finite_faces_begin(); f != t.finite_faces_end(); ++f){
  55.         visited[f] = -1;
  56.     }
  57.        
  58.     for(int i=0; i<m; ++i){
  59.         P p; cin >> p;
  60.         double d; cin >> d;
  61.        
  62.         //check if nearest infection is closer than minimum distance. sqrt(d) = r. d = r^2.
  63.         P nearest = t.nearest_vertex(p)->point();
  64.         if(CGAL::squared_distance(nearest, p) < d){
  65.             cout << "n"; continue;
  66.         }
  67.         FH start_face = t.locate(p);
  68.         if(t.is_infinite(start_face) || dfs(start_face, visited, t, d, i)) cout << "y";
  69.         else cout <<"n";
  70.     }
  71.     cout << endl;
  72. }
  73.  
  74. int main(){
  75.     ios_base::sync_with_stdio(false);
  76.     for(int n; cin >> n && n>0;) do_testcases(n);
  77.     return 0;
  78. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement