#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Delaunay_triangulation_2.h>
#include <CGAL/Triangulation_vertex_base_with_info_2.h>
#include <CGAL/Triangulation_face_base_2.h>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/prim_minimum_spanning_tree.hpp>

typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS,
                              boost::property<boost::vertex_distance_t, long>,
                              boost::property<boost::edge_weight_t, long>>
    w_graph;

typedef boost::property_map<w_graph, boost::edge_weight_t>::type w_map;
typedef boost::property_map<w_graph, boost::vertex_distance_t>::type d_map;
typedef boost::property_map<w_graph, boost::vertex_index_t>::type i_map;
typedef boost::graph_traits<w_graph>::edge_descriptor edge_desc;
typedef boost::graph_traits<w_graph>::vertex_descriptor vert_desc;

typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef CGAL::Triangulation_vertex_base_with_info_2<int, K> Vb;
typedef CGAL::Triangulation_face_base_2<K> Fb;
typedef CGAL::Triangulation_data_structure_2<Vb, Fb> Tds;
typedef CGAL::Delaunay_triangulation_2<K, Tds> Triangulation;
typedef Triangulation::Edge_iterator Edge_iterator;
typedef Triangulation::Vertex_handle Vh;
typedef K::Segment_2 Edge;
typedef K::Point_2 Point;

void testcase(){
    int n, m;
    int x, y;
    long p;

    cin >> n >> m >> p;
    std::vector<pair<Point, int>> jammers(n);
    std::vector<K::Point_2> missions_start(m);
    std::vector<K::Point_2> missions_end(m);

    for (int i = 0; i < n; ++i)
    {
        std::cin >> x >> y;
        jammers[i] = make_pair(Point(x, y), i);
    }

    for (int i = 0; i < m; ++i)
    {
        cin >> x >> y;
        missions_start[i] = Point(x, y);
        cin >> x >> y;
        missions_end[i] = Point(x, y);
    }

    // construct triangulation
    Triangulation t;
    t.insert(jammers.begin(), jammers.end());

    for (Edge_iterator e = t.finite_edges_begin(); e != t.finite_edges_end(); ++e)
    {
        //Grab the 2 vertex handles for the end points
        Vh vi = e->first->vertex((e->second + 1) % 3);
        Vh vj = e->first->vertex((e->second + 2) % 3);

        long cur_dist = CGAL::squared_distance(vi->point(), vj->point());
        boost::add_edge(vi->info(), vj->info(), cur_dist, G);

        //create lookup for triangulation points and their index in bgl
        vertex_to_graph_index[vi->point()] = vi->info();
        vertex_to_graph_index[vj->point()] = vj->info();
        //and the other way around
        graph_index_to_vertex[vi->info()] = vi->point();
        graph_index_to_vertex[vj->info()] = vj->point();
    }
    //At the end I should have n vertices in the graph
    long longest_dist_in_dijkstra = 0;
    long longest_dist_uncovered = 0;
    for (int i = 0; i < m; ++i)
    {

        Point nearest = t.nearest_vertex(missions_start[i])->point();
        long cur_dist = CGAL::squared_distance(missions_start[i], nearest);
        boost::add_edge(n, vertex_to_graph_index[nearest], cur_dist,
        max_mission_dist[i] = max(max_mission_dist[i], cur_dist);
        //update lookup for mission start
        graph_index_to_vertex[n] = missions_start[i];
        vertex_to_graph_index[missions_start[i]] = n;

        nearest = t.nearest_vertex(missions_end[i])->point();
        cur_dist = CGAL::squared_distance(missions_end[i], nearest);
        boost::add_edge(vertex_to_graph_index[nearest], n + 1, cur_dist, G);
        max_mission_dist[i] = max(max_mission_dist[i], cur_dist);
        //update lookup for mission end
        graph_index_to_vertex[n + 1] = missions_end[i];
        vertex_to_graph_index[missions_end[i]] = n + 1;


        d_map distance = boost::get(boost::vertex_distance, G);
        std::vector<vert_desc> pred_map(n + 2);

        boost::dijkstra_shortest_paths(G, n,
                                       boost::distance_map(distance)
                                           .predecessor_map(boost::make_iterator_property_map(
                                               pred_map.begin(), boost::get(boost::vertex_index, G))));

        boost::graph_traits<w_graph>::vertex_iterator v, vend;

        // cout << "finished dijkstra" << endl;
        longest_dist_uncovered = max(longest_dist_uncovered, max_mission_dist[i]);

        //I have n vertices before adding mission start and end. Mission start will have index n, mission end will
        //have index n+1
        int cur = n + 1;
        while (n != cur)
        {
            // cout << cur << " ";
            Point end = graph_index_to_vertex[cur];
            cur = pred_map[cur];
            Point start = graph_index_to_vertex[cur];
            long dist = CGAL::squared_distance(end, start);
            if (cur != n && cur != n + 1)
                longest_dist_in_dijkstra = max(longest_dist_in_dijkstra, dist);
        }
        //compute a and b coefficients, check if mission start and end are reachable
        //....

        //remove the mission start and end point and associated edges s.t I can reuse the same indices for the next
        //mission
        boost::clear_vertex(n, G);
        boost::clear_vertex(n+1, G);
        boost::remove_vertex(n,G);
        boost::remove_vertex(n+1,G);
    }
}