test/aoj/2423.test.cpp

View this file on GitHub
Last update: 2024-09-28 19:54:09+09:00
Problem: https://onlinejudge.u-aizu.ac.jp/problems/2423

Depends on

Code

// competitive-verifier: PROBLEM https://onlinejudge.u-aizu.ac.jp/problems/2423
// competitive-verifier: TLE 0.5
// competitive-verifier: MLE 64
// 辞書順マッチングのverify
#include <iostream>
#include <vector>
#include "src/Graph/BipartiteGraph.hpp"
#include "src/Geometry/Circle.hpp"
#include "src/Geometry/min_enclosing_circle.hpp"
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(false);
 using namespace geo;
 using R= long double;
 int n, m;
 cin >> n >> m;
 BipartiteGraph bg(m, n);
 R rs[n];
 for (int i= 0; i < n; i++) cin >> rs[i];
 for (int j= 0; j < m; j++) {
  int p;
  cin >> p;
  vector<Point<R>> ps(p);
  for (int k= 0; k < p; k++) cin >> ps[k];
  R r= min_enclosing_circle(ps).r;
  for (int i= 0; i < n; i++)
   if (sgn(rs[i] - r) >= 0) bg.add_edge(j, i + m);
 }
 auto [mc, mate]= bipartite_matching<true>(bg);
 if (mc.size() < m) cout << "NG" << '\n';
 else
  for (int l= 0; l < m; ++l) cout << mate[l] - m + 1 << '\n';
 return 0;
}

#line 1 "test/aoj/2423.test.cpp"
// competitive-verifier: PROBLEM https://onlinejudge.u-aizu.ac.jp/problems/2423
// competitive-verifier: TLE 0.5
// competitive-verifier: MLE 64
// 辞書順マッチングのverify
#include <iostream>
#include <vector>
#line 2 "src/Graph/BipartiteGraph.hpp"
#include <cassert>
#include <tuple>
#include <algorithm>
#line 4 "src/Internal/ListRange.hpp"
#include <iterator>
#include <type_traits>
#define _LR(name, IT, CT) \
 template <class T> struct name { \
  using Iterator= typename std::vector<T>::IT; \
  Iterator bg, ed; \
  Iterator begin() const { return bg; } \
  Iterator end() const { return ed; } \
  size_t size() const { return std::distance(bg, ed); } \
  CT &operator[](int i) const { return bg[i]; } \
 }
_LR(ListRange, iterator, T);
_LR(ConstListRange, const_iterator, const T);
#undef _LR
template <class T> struct CSRArray {
 std::vector<T> dat;
 std::vector<int> p;
 size_t size() const { return p.size() - 1; }
 ListRange<T> operator[](int i) { return {dat.begin() + p[i], dat.begin() + p[i + 1]}; }
 ConstListRange<T> operator[](int i) const { return {dat.cbegin() + p[i], dat.cbegin() + p[i + 1]}; }
};
template <template <class> class F, class T> std::enable_if_t<std::disjunction_v<std::is_same<F<T>, ListRange<T>>, std::is_same<F<T>, ConstListRange<T>>, std::is_same<F<T>, CSRArray<T>>>, std::ostream &> operator<<(std::ostream &os, const F<T> &r) {
 os << '[';
 for (int _= 0, __= r.size(); _ < __; ++_) os << (_ ? ", " : "") << r[_];
 return os << ']';
}
#line 3 "src/Graph/Graph.hpp"
struct Edge: std::pair<int, int> {
 using std::pair<int, int>::pair;
 Edge &operator--() { return --first, --second, *this; }
 int to(int v) const { return first ^ second ^ v; }
 friend std::istream &operator>>(std::istream &is, Edge &e) { return is >> e.first >> e.second, is; }
};
struct Graph: std::vector<Edge> {
 size_t n;
 Graph(size_t n= 0, size_t m= 0): vector(m), n(n) {}
 size_t vertex_size() const { return n; }
 size_t edge_size() const { return size(); }
 size_t add_vertex() { return n++; }
 size_t add_edge(int s, int d) { return emplace_back(s, d), size() - 1; }
 size_t add_edge(Edge e) { return emplace_back(e), size() - 1; }
#define _ADJ_FOR(a, b) \
 for (auto [u, v]: *this) a; \
 for (size_t i= 0; i < n; ++i) p[i + 1]+= p[i]; \
 for (int i= size(); i--;) { \
  auto [u, v]= (*this)[i]; \
  b; \
 }
#define _ADJ(a, b) \
 vector<int> p(n + 1), c(size() << !dir); \
 if (!dir) { \
  _ADJ_FOR((++p[u], ++p[v]), (c[--p[u]]= a, c[--p[v]]= b)) \
 } else if (dir > 0) { \
  _ADJ_FOR(++p[u], c[--p[u]]= a) \
 } else { \
  _ADJ_FOR(++p[v], c[--p[v]]= b) \
 } \
 return {c, p}
 CSRArray<int> adjacency_vertex(int dir) const { _ADJ(v, u); }
 CSRArray<int> adjacency_edge(int dir) const { _ADJ(i, i); }
#undef _ADJ
#undef _ADJ_FOR
};
#line 6 "src/Graph/BipartiteGraph.hpp"
// [0, L) is left, [L, n) is right
struct BipartiteGraph: Graph {
 size_t L;
 BipartiteGraph() {}
 BipartiteGraph(size_t L, size_t R, size_t m= 0): Graph(L + R, m), L(L) {}
 size_t left_size() const { return L; }
 size_t right_size() const { return this->n - L; }
};
std::vector<int> paint_two_colors(const CSRArray<int> &adj) {
 const int n= adj.size();
 std::vector<int> col(n, -1);
 for (int s= n; s--;)
  if (col[s] == -1) {
   std::vector<int> q= {s};
   for (int i= col[s]= 0, v; i < (int)q.size(); ++i)
    for (int u: adj[v= q[i]])
     if (int c= col[v]; col[u] == c) return {};
     else if (col[u] == -1) col[u]= c ^ 1, q.push_back(u);
  }
 return col;
}
std::vector<int> paint_two_colors(const Graph &g) { return paint_two_colors(g.adjacency_vertex(0)); }
// { BipartiteGraph , original to new, new to original }
// {{},{},{}} if not bipartite
std::tuple<BipartiteGraph, std::vector<int>, std::vector<int>> graph_to_bipartite(const Graph &g, std::vector<int> color= {}) {
 if (color.empty()) color= paint_two_colors(g);
 if (color.empty()) return {};
 const int n= g.vertex_size(), m= g.edge_size();
 std::vector<int> a(n), b(n);
 int l= 0, r= n;
 for (int i= n; i--;) b[a[i]= color[i] ? --r : l++]= i;
 BipartiteGraph bg(l, n - l, m);
 for (int i= m; i--;) {
  auto [u, v]= g[i];
  bg[i]= std::minmax(a[u], a[v]);
 }
 return {bg, a, b};
}
namespace _bg_internal {
std::vector<int> _bm(int L, const CSRArray<int> &adj, std::vector<int> &m) {
 std::vector<int> a, p, q(L);
 for (bool u= true; u;) {
  u= false, a.assign(L, -1), p.assign(L, -1);
  int t= 0;
  for (int l= L; l--;)
   if (m[l] == -1) q[t++]= a[l]= p[l]= l;
  for (int i= 0; i < t; ++i)
   if (int l= q[i], x; m[a[l]] == -1)
    for (int r: adj[l]) {
     if (x= m[r]; x == -1) {
      for (u= true; r != -1; l= p[l]) m[r]= l, std::swap(m[l], r);
      break;
     }
     if (p[x] == -1) a[q[t++]= x]= a[p[x]= l];
    }
 }
 return a;
}
}
template <bool lexical= false> std::pair<std::vector<int>, std::vector<int>> bipartite_matching(const BipartiteGraph &bg, std::vector<int> partner= {}) {
 const int L= bg.left_size(), M= bg.edge_size();
 if (partner.empty()) partner.assign(bg.vertex_size(), -1);
 assert(partner.size() == bg.vertex_size());
 {
  CSRArray<int> adj{std::vector<int>(M), std::vector<int>(L + 1)};
  for (auto [l, r]: bg) ++adj.p[l];
  for (int i= 0; i < L; ++i) adj.p[i + 1]+= adj.p[i];
  for (auto [l, r]: bg) adj.dat[--adj.p[l]]= r;
  if constexpr (lexical) {
   for (int l= L; l--;) std::sort(adj[l].begin(), adj[l].end());
   _bg_internal::_bm(L, adj, partner);
   std::vector<char> a(L, 1);
   for (int l= 0; l < L; ++l)
    if (int r= partner[l], v= l; r != -1) {
     std::vector<int> p(L, partner[v]= partner[r]= -1), c(adj.p.begin(), adj.p.begin() + L);
     for (p[v]= -2;;) {
      if (c[v] == adj.p[v + 1]) v= p[v];
      else if (int u= partner[r= adj.dat[c[v]++]]; u == -1) {
       for (; r != -1; v= p[v]) partner[r]= v, std::swap(partner[v], r);
       break;
      } else if (a[u] && p[u] == -1) p[u]= v, v= u;
     }
     a[l]= 0;
    }
  } else _bg_internal::_bm(L, adj, partner);
 }
 std::vector<int> c;
 std::vector<char> p(L);
 for (int i= 0; i < M; ++i)
  if (auto [l, r]= bg[i]; partner[l] == r && !p[l]) c.push_back(i), p[l]= 1;
 return {c, partner};
}
#line 3 "src/Geometry/Point.hpp"
#include <fstream>
#include <iomanip>
#include <cmath>
#line 2 "src/Internal/long_traits.hpp"
// clang-format off
template<class T>struct make_long{using type= T;};
template<>struct make_long<char>{using type= short;};
template<>struct make_long<unsigned char>{using type= unsigned short;};
template<>struct make_long<short>{using type= int;};
template<>struct make_long<unsigned short>{using type= unsigned;};
template<>struct make_long<int>{using type= long long;};
template<>struct make_long<unsigned>{using type= unsigned long long;};
template<>struct make_long<long long>{using type= __int128_t;};
template<>struct make_long<unsigned long long>{using type= __uint128_t;};
template<>struct make_long<float>{using type= double;};
template<>struct make_long<double>{using type= long double;};
template<class T> using make_long_t= typename make_long<T>::type;
// clang-format on
#line 8 "src/Geometry/Point.hpp"
namespace geo {
using namespace std;
struct Visualizer {
 ofstream ofs;
 Visualizer(string s= "visualize.txt"): ofs(s) { ofs << fixed << setprecision(10); }
 friend Visualizer &operator<<(Visualizer &vis, const string &s) { return vis.ofs << s, vis; }
};
template <class K> int sgn(K x) {
 if constexpr (is_floating_point_v<K>) {
  static constexpr K EPS= 1e-9;
  return x < -EPS ? -1 : x > EPS;
 } else return x < 0 ? -1 : x > 0;
}
template <class K> K err_floor(K x) {
 K y= floor(x);
 if constexpr (is_floating_point_v<K>)
  if (K z= y + 1, w= x - z; 0 <= sgn(w) && sgn(w - 1) < 0) return z;
 return y;
}
template <class K> K err_ceil(K x) {
 K y= ceil(x);
 if constexpr (is_floating_point_v<K>)
  if (K z= y - 1, w= x - z; 0 < sgn(w + 1) && sgn(w) <= 0) return z;
 return y;
}
template <class K> struct Point {
 K x, y;
 Point(K x= K(), K y= K()): x(x), y(y) {}
 Point &operator+=(const Point &p) { return x+= p.x, y+= p.y, *this; }
 Point &operator-=(const Point &p) { return x-= p.x, y-= p.y, *this; }
 Point &operator*=(K a) { return x*= a, y*= a, *this; }
 Point &operator/=(K a) { return x/= a, y/= a, *this; }
 Point operator+(const Point &p) const { return {x + p.x, y + p.y}; }
 Point operator-(const Point &p) const { return {x - p.x, y - p.y}; }
 Point operator*(K a) const { return {x * a, y * a}; }
 Point operator/(K a) const { return {x / a, y / a}; }
 friend Point operator*(K a, const Point &p) { return {a * p.x, a * p.y}; }
 Point operator-() const { return {-x, -y}; }
 bool operator<(const Point &p) const {
  int s= sgn(x - p.x);
  return s ? s < 0 : sgn(y - p.y) < 0;
 }
 bool operator>(const Point &p) const { return p < *this; }
 bool operator<=(const Point &p) const { return !(p < *this); }
 bool operator>=(const Point &p) const { return !(*this < p); }
 bool operator==(const Point &p) const { return !sgn(x - p.x) && !sgn(y - p.y); }
 bool operator!=(const Point &p) const { return sgn(x - p.x) || sgn(y - p.y); }
 Point operator!() const { return {-y, x}; }  // rotate 90 degree
 friend istream &operator>>(istream &is, Point &p) { return is >> p.x >> p.y; }
 friend ostream &operator<<(ostream &os, const Point &p) { return os << "(" << p.x << ", " << p.y << ")"; }
 friend Visualizer &operator<<(Visualizer &vis, const Point &p) { return vis.ofs << p.x << " " << p.y << "\n", vis; }
};
template <class K> make_long_t<K> dot(const Point<K> &p, const Point<K> &q) { return make_long_t<K>(p.x) * q.x + make_long_t<K>(p.y) * q.y; }
// left turn: > 0, right turn: < 0
template <class K> make_long_t<K> cross(const Point<K> &p, const Point<K> &q) { return make_long_t<K>(p.x) * q.y - make_long_t<K>(p.y) * q.x; }
template <class K> make_long_t<K> norm2(const Point<K> &p) { return dot(p, p); }
template <class K> long double norm(const Point<K> &p) { return sqrt(norm2(p)); }
template <class K> make_long_t<K> dist2(const Point<K> &p, const Point<K> &q) { return norm2(p - q); }
template <class T, class U> long double dist(const T &a, const U &b) { return sqrt(dist2(a, b)); }
enum CCW { COUNTER_CLOCKWISE, CLOCKWISE, ONLINE_BACK, ONLINE_FRONT, ON_SEGMENT };
ostream &operator<<(ostream &os, CCW c) { return os << (c == COUNTER_CLOCKWISE ? "COUNTER_CLOCKWISE" : c == CLOCKWISE ? "CLOCKWISE" : c == ONLINE_BACK ? "ONLINE_BACK" : c == ONLINE_FRONT ? "ONLINE_FRONT" : "ON_SEGMENT"); }
template <class K> CCW ccw(const Point<K> &p0, const Point<K> &p1, const Point<K> &p2) {
 Point a= p1 - p0, b= p2 - p0;
 int s;
 if constexpr (is_floating_point_v<K>) s= sgn(sgn(cross(a, b) / sqrt(norm2(a) * norm2(b))));
 else s= sgn(cross(a, b));
 if (s) return s > 0 ? COUNTER_CLOCKWISE : CLOCKWISE;
 if (K d= dot(a, b); sgn(d) < 0) return ONLINE_BACK;
 else return sgn(d - norm2(a)) > 0 ? ONLINE_FRONT : ON_SEGMENT;
}
template <class K> struct Line;
template <class K> struct Segment;
template <class K> class Polygon;
template <class K> struct Convex;
template <class K> struct Affine {
 K a00= 1, a01= 0, a10= 0, a11= 1;
 Point<K> b;
 Point<K> operator()(const Point<K> &p) const { return {a00 * p.x + a01 * p.y + b.x, a10 * p.x + a11 * p.y + b.y}; }
 Line<K> operator()(const Line<K> &l);
 Segment<K> operator()(const Segment<K> &s);
 Polygon<K> operator()(const Polygon<K> &p);
 Convex<K> operator()(const Convex<K> &c);
 Affine operator*(const Affine &r) const { return {a00 * r.a00 + a01 * r.a10, a00 * r.a01 + a01 * r.a11, a10 * r.a00 + a11 * r.a10, a10 * r.a01 + a11 * r.a11, (*this)(r)}; }
 Affine &operator*=(const Affine &r) { return *this= *this * r; }
};
template <class K> Affine<K> translate(const Point<K> &p) { return {1, 0, 0, 1, p}; }
}
#line 4 "src/Geometry/Line.hpp"
namespace geo {
template <class K> struct Line {
 using P= Point<K>;
 P p, d;  // p+td
 Line() {}
 // p + td
 Line(const P &p, const P &d): p(p), d(d) { assert(sgn(norm2(d))); }
 // ax+by+c=0 ................. ax+by+c>0: left, ax+by+c=0: on, ax+by+c<0: right
 Line(K a, K b, K c) {
  int sa= sgn(a), sb= sgn(b);
  assert(sa || sb);
  d= P{b, -a}, p= sb ? P{0, -c / b} : P{-c / a, 0};
 }
 bool operator==(const Line &l) const { return !sgn(cross(d, l.d)) && !where(l.p); }
 bool operator!=(const Line &l) const { return sgn(cross(d, l.d)) || where(l.p); }
 // +1: left, 0: on, -1: right
 int where(const P &q) const { return sgn(cross(d, q - p)); }
 P project(const P &q) const { return p + dot(q - p, d) / norm2(d) * d; }
 // return  a,b,c of ax+by+c=0
 tuple<K, K, K> coef() const { return make_tuple(-d.y, d.x, cross(p, d)); }
 friend ostream &operator<<(ostream &os, const Line &l) { return os << l.p << " + t" << l.d; }
 friend Visualizer &operator<<(Visualizer &vis, const Line &l) {
  auto [a, b, c]= l.coef();
  return vis.ofs << "Line " << a << " " << b << " " << c << "\n", vis;
 }
};
// p + t(q-p)
template <class K> Line<K> line_through(const Point<K> &p, const Point<K> &q) { return Line(p, q - p); }
template <class K> bool is_parallel(const Line<K> &l, const Line<K> &m) { return !sgn(cross(l.d, m.d)); }
template <class K> bool is_orthogonal(const Line<K> &l, const Line<K> &m) { return !sgn(dot(l.d, m.d)); }
// 1 : properly crossing, 0 : disjoint parallel, 2 : same line
template <class K> vector<Point<K>> cross_points(const Line<K> &l, const Line<K> &m) {
 K a= cross(m.d, l.d), b= cross(l.p - m.p, l.d);
 if (sgn(a)) return {m.p + b / a * m.d};  // properly crossing
 if (sgn(b)) return {};                   // disjoint parallel
 return {m.p, m.p + m.d};                 // same line
}
// perpendicular bisector ............ p on leftside
template <class K> Line<K> bisector(const Point<K> &p, const Point<K> &q) { return Line((p + q) / 2, !(q - p)); }
// angle bisector ........... parallel -> 1 line, non-parallel -> 2 lines
template <class K> vector<Line<K>> bisector(const Line<K> &l, const Line<K> &m) {
 auto cp= cross_points(l, m);
 if (cp.size() != 1) return {Line((l.p + m.p) / 2, l.d)};
 auto d= l.d / norm(l.d) + m.d / norm(m.d);
 return {Line(cp[0], d), Line(cp[0], !d)};
}
template <class K> make_long_t<K> dist2(const Line<K> &l, const Point<K> &p) {
 make_long_t<K> a= cross(l.d, p - l.p);
 return a * a / norm2(l.d);
}
template <class K> make_long_t<K> dist2(const Point<K> &p, const Line<K> &l) { return dist2(l, p); }
template <class K> make_long_t<K> dist2(const Line<K> &l, const Line<K> &m) { return is_parallel(l, m) ? dist2(l, m.p) : 0; }
template <class K> Affine<K> reflect(const Line<K> &l) {
 K a= l.d.x * l.d.x, b= l.d.x * l.d.y * 2, c= l.d.y * l.d.y, d= a + c;
 a/= d, b/= d, c/= d, d= a - c;
 return {d, b, b, -d, Point<K>{c * 2 * l.p.x - b * l.p.y, a * 2 * l.p.y - b * l.p.x}};
}
template <class K> Line<K> Affine<K>::operator()(const Line<K> &l) { return line_through((*this)(l.p), (*this)(l.p + l.d)); }
}
#line 4 "src/Geometry/Segment.hpp"
namespace geo {
template <class K> struct Segment {
 using P= Point<K>;
 P p, q;
 Segment() {}
 Segment(const P &p, const P &q): p(p), q(q) {}
 // do not consider the direction
 bool operator==(const Segment &s) const { return (p == s.p && q == s.q) || (p == s.q && q == s.p); }
 bool operator!=(const Segment &s) const { return !(*this == s); }
 bool on(const P &r) const { return ccw(p, q, r) == ON_SEGMENT; }
 P &operator[](int i) { return i ? q : p; }
 const P &operator[](int i) const { return i ? q : p; }
 long double length() const { return dist(p, q); }
 P closest_point(const P &r) const {
  P d= q - p;
  K a= dot(r - p, d), b;
  return sgn(a) > 0 ? sgn(a - (b= norm2(d))) < 0 ? p + a / b * d : q : p;
 }
 friend ostream &operator<<(ostream &os, const Segment &s) { return os << s.p << "---" << s.q; }
 friend Visualizer &operator<<(Visualizer &vis, const Segment &s) { return vis.ofs << "Segment " << s.p.x << " " << s.p.y << " " << s.q.x << " " << s.q.y << "\n", vis; }
};
// 1: properly crossing, 0: no intersect, 2: same line
template <class K> vector<Point<K>> cross_points(const Segment<K> &s, const Line<K> &l) {
 Point d= s.q - s.p;
 K a= cross(d, l.d), b= cross(l.p - s.p, l.d);
 if (sgn(a)) {
  if (b/= a; sgn(b) < 0 || sgn(b - 1) > 0) return {};  // no intersect
  else return {s.p + b * d};                           // properly crossing}
 }
 if (sgn(b)) return {};  // disjoint parallel
 return {s.p, s.q};      // same line
}
template <class K> vector<Point<K>> cross_points(const Line<K> &l, const Segment<K> &s) { return cross_points(s, l); }
// 2: same line, 0: no intersect, 1: ...
template <class K> vector<Point<K>> cross_points(const Segment<K> &s, const Segment<K> &t) {
 Point d= s.q - s.p, e= t.q - t.p;
 K a= cross(d, e), b= cross(t.p - s.p, e);
 if (sgn(a)) {
  if (b/= a; sgn(b) < 0 || sgn(b - 1) > 0) return {};                       // no intersect
  if (b= cross(d, s.p - t.p) / a; sgn(b) < 0 || sgn(b - 1) > 0) return {};  // no intersect
  return {t.p + b * e};                                                     // properly crossing
 }
 if (sgn(b)) return {};  // disjoint parallel
 vector<Point<K>> ps;    // same line
 auto insert_if_possible= [&](const Point<K> &p) {
  for (auto q: ps)
   if (p == q) return;
  ps.emplace_back(p);
 };
 if (sgn(dot(t.p - s.p, t.q - s.p)) <= 0) insert_if_possible(s.p);
 if (sgn(dot(t.p - s.q, t.q - s.q)) <= 0) insert_if_possible(s.q);
 if (sgn(dot(s.p - t.p, s.q - t.p)) <= 0) insert_if_possible(t.p);
 if (sgn(dot(s.p - t.q, s.q - t.q)) <= 0) insert_if_possible(t.q);
 return ps;
}
enum INTERSECTION { CROSSING, TOUCHING, DISJOINT, OVERLAP };
ostream &operator<<(ostream &os, INTERSECTION i) { return os << (i == CROSSING ? "CROSSING" : i == TOUCHING ? "TOUCHING" : i == DISJOINT ? "DISJOINT" : "OVERLAP"); }
template <class K> INTERSECTION intersection(const Segment<K> &s, const Segment<K> &t) {
 auto cp= cross_points(s, t);
 return cp.size() == 0 ? DISJOINT : cp.size() == 2 ? OVERLAP : cp[0] == s.p || cp[0] == s.q || cp[0] == t.p || cp[0] == t.q ? TOUCHING : CROSSING;
}
template <class K> make_long_t<K> dist2(const Segment<K> &s, const Point<K> &p) { return dist2(p, s.closest_point(p)); }
template <class K> make_long_t<K> dist2(const Point<K> &p, const Segment<K> &s) { return dist2(s, p); }
template <class K> make_long_t<K> dist2(const Segment<K> &s, const Line<K> &l) { return cross_points(s, l).size() ? 0 : min(dist2(s.p, l), dist2(s.q, l)); }
template <class K> make_long_t<K> dist2(const Line<K> &l, const Segment<K> &s) { return dist2(s, l); }
template <class K> make_long_t<K> dist2(const Segment<K> &s, const Segment<K> &t) { return cross_points(s, t).size() ? 0 : min({dist2(s, t.p), dist2(s, t.q), dist2(t, s.p), dist2(t, s.q)}); }
template <class K> Segment<K> Affine<K>::operator()(const Segment<K> &s) { return {(*this)(s.p), (*this)(s.q)}; }
}
#line 3 "src/Geometry/Circle.hpp"
namespace geo {
template <class R> struct Circle {
 using P= Point<R>;
 P o;
 R r;
 Circle() {}
 Circle(const P &o, R r): o(o), r(r) {}
 long double area() const { return r * r * M_PI; }
 // +1: in, 0: on, -1: out
 int where(const P &p) const { return sgn(r * r - dist2(p, o)); }
 // +1: intersect, 0: contact, -1: disjoint
 int where(const Line<R> &l) const { return sgn(r * r - dist2(l, o)); }
 // true: c in *this
 bool in(const Circle &c) const {
  R a= c.r - r;
  return sgn(a) <= 0 && sgn(dist2(o, c.o) - a * a) <= 0;
 }
 vector<Line<R>> tangent(const P &p) const {
  P d= p - o, e= !d;
  R b= norm2(d), a= b - r * r;
  if (int s= sgn(a); s < 0) return {};
  else if (s == 0) return {{p, e}};
  d*= r, e*= sqrt(a);
  return {Line(p, !(d + e)), Line(p, !(d - e))};
 }
 friend ostream &operator<<(ostream &os, const Circle &c) { return os << c.o << " " << c.r; }
 friend Visualizer &operator<<(Visualizer &vis, const Circle &c) { return vis.ofs << "Circle " << c.o.x << " " << c.o.y << " " << c.r << '\n', vis; }
};
// 2: properly intersect, 1: contact, 0: disjoint, 3: same
// counter-clockwise of c and clockwise of d
template <class R> vector<Point<R>> cross_points(const Circle<R> &c, const Circle<R> &d) {
 Point v= d.o - c.o;
 R g= norm2(v), a= c.r - d.r, b= c.r + d.r;
 if (!sgn(g)) {
  if (sgn(a)) return {};
  return {{c.o.x + c.r, c.o.y}, {c.o.x - c.r, c.o.y}, {c.o.x, c.o.y + c.r}};
 }
 int in= sgn(g - a * a), out= sgn(g - b * b);
 if (in < 0 || out > 0) return {};
 if (!in) return {(c.r * d.o - d.r * c.o) / a};
 if (!out) return {(c.r * d.o + d.r * c.o) / b};
 R e= (a * b + g) / (g * 2);
 Point q= c.o + e * v, n= !v * sqrt(c.r * c.r / g - e * e);
 return {q - n, q + n};
}
// 2: properly intersect, 1: contact, 0: disjoint
// direction of l
template <class R> vector<Point<R>> cross_points(const Circle<R> &c, const Line<R> &l) {
 Point<R> v= l.p - c.o;
 R a= norm2(l.d), b= dot(l.d, v) / a, d= b * b - (norm2(v) - c.r * c.r) / a;
 int s= sgn(d);
 if (s < 0) return {};
 if (!s) return {l.p - b * l.d};
 d= sqrt(d);
 return {l.p - (b + d) * l.d, l.p - (b - d) * l.d};
}
template <class R> vector<Point<R>> cross_points(const Line<R> &l, const Circle<R> &c) { return cross_points(c, l); }
template <class R> vector<Point<R>> cross_points(const Circle<R> &c, const Segment<R> &s) {
 Point<R> u= s.q - s.p, v= s.p - c.o;
 R a= norm2(u), b= dot(u, v) / a, d= b * b - (norm2(v) - c.r * c.r) / a;
 int t= sgn(d);
 if (t < 0) return {};
 if (!t && sgn(b) <= 0 && sgn(1 + b) >= 0) return {s.p - b * u};
 d= sqrt(d), a= -b - d, b= -b + d;
 vector<Point<R>> ps;
 if (0 <= sgn(a) && sgn(a - 1) <= 0) ps.emplace_back(s.p + a * u);
 if (0 <= sgn(b) && sgn(b - 1) <= 0) ps.emplace_back(s.p + b * u);
 return ps;
}
template <class R> vector<Point<R>> cross_points(const Segment<R> &s, const Circle<R> &c) { return cross_points(c, s); }
template <class R> Circle<R> circumscribed_circle(const Point<R> &A, const Point<R> &B, const Point<R> &C) {
 Point u= !(B - A), v= C - A, o= (A + B + dot(C - B, v) / dot(u, v) * u) / 2;
 return {o, dist(A, o)};
}
template <class R> Circle<R> inscribed_circle(const Point<R> &A, const Point<R> &B, const Point<R> &C) {
 R a= dist(B, C), b= dist(C, A), c= dist(A, B), s= (a + b + c) / 2;
 return {(a * A + b * B + c * C) / (s * 2), sqrt((s - a) * (s - b) * (s - c) / s)};
}
template <class R> vector<Line<R>> common_tangent(const Circle<R> &c, const Circle<R> &d) {
 Point u= d.o - c.o, v= !u;
 R g= norm2(u), b;
 if (!sgn(g)) return {};  // same origin
 vector<Line<R>> ls;
 for (R a: {c.r - d.r, c.r + d.r}) {
  if (int s= sgn(b= g - a * a); !s) ls.emplace_back(Line(c.o + c.r * a / g * u, v));
  else if (s > 0) {
   Point x= a / g * u, y= sqrt(b) / g * v, e= x + y, f= x - y;
   ls.emplace_back(Line(c.o + c.r * e, !e)), ls.emplace_back(Line(c.o + c.r * f, !f));
  }
 }
 return ls;
}
}
#line 2 "src/Misc/rng.hpp"
#include <random>
#include <cstdint>
uint64_t rng() {
 static uint64_t x= 10150724397891781847ULL * std::random_device{}();
 return x^= x << 7, x^= x >> 9;
}
uint64_t rng(uint64_t lim) { return rng() % lim; }
int64_t rng(int64_t l, int64_t r) { return l + rng() % (r - l); }
#line 4 "src/Geometry/min_enclosing_circle.hpp"
namespace geo {
template <class R> Circle<R> min_enclosing_circle(vector<Point<R>> ps) {
 assert(ps.size());
 if (ps.size() == 1) return {ps[0], 0.};
 const int n= ps.size();
 for (int i= n; --i;) swap(ps[i], ps[rng(i + 1)]);
 Circle c= {(ps[0] + ps[1]) / 2, dist(ps[0], ps[1]) / 2};
 for (int i= 2; i < n; ++i)
  if (c.where(ps[i]) == -1) {
   c= {(ps[0] + ps[i]) / 2, dist(ps[0], ps[i]) / 2};
   for (int j= 1; j < i; ++j)
    if (c.where(ps[j]) == -1) {
     c= {(ps[i] + ps[j]) / 2, dist(ps[i], ps[j]) / 2};
     for (int k= 0; k < j; ++k)
      if (c.where(ps[k]) == -1) c= circumscribed_circle(ps[i], ps[j], ps[k]);
    }
  }
 return c;
}
}
#line 10 "test/aoj/2423.test.cpp"
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(false);
 using namespace geo;
 using R= long double;
 int n, m;
 cin >> n >> m;
 BipartiteGraph bg(m, n);
 R rs[n];
 for (int i= 0; i < n; i++) cin >> rs[i];
 for (int j= 0; j < m; j++) {
  int p;
  cin >> p;
  vector<Point<R>> ps(p);
  for (int k= 0; k < p; k++) cin >> ps[k];
  R r= min_enclosing_circle(ps).r;
  for (int i= 0; i < n; i++)
   if (sgn(rs[i] - r) >= 0) bg.add_edge(j, i + m);
 }
 auto [mc, mate]= bipartite_matching<true>(bg);
 if (mc.size() < m) cout << "NG" << '\n';
 else
  for (int l= 0; l < m; ++l) cout << mate[l] - m + 1 << '\n';
 return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++-13	testcase_00	AC	6 ms	4 MB
g++-13	testcase_01	AC	5 ms	4 MB
g++-13	testcase_02	AC	6 ms	4 MB
g++-13	testcase_03	AC	5 ms	4 MB
g++-13	testcase_04	AC	6 ms	4 MB
g++-13	testcase_05	AC	5 ms	4 MB
g++-13	testcase_06	AC	5 ms	4 MB
g++-13	testcase_07	AC	5 ms	4 MB
g++-13	testcase_08	AC	5 ms	4 MB
g++-13	testcase_09	AC	5 ms	4 MB
g++-13	testcase_10	AC	5 ms	4 MB
g++-13	testcase_11	AC	5 ms	4 MB
g++-13	testcase_12	AC	5 ms	4 MB
g++-13	testcase_13	AC	4 ms	4 MB
g++-13	testcase_14	AC	5 ms	4 MB
g++-13	testcase_15	AC	6 ms	4 MB
g++-13	testcase_16	AC	5 ms	4 MB
g++-13	testcase_17	AC	6 ms	4 MB
g++-13	testcase_18	AC	5 ms	4 MB
g++-13	testcase_19	AC	6 ms	4 MB
g++-13	testcase_20	AC	7 ms	4 MB
clang++-18	testcase_00	AC	6 ms	4 MB
clang++-18	testcase_01	AC	5 ms	4 MB
clang++-18	testcase_02	AC	6 ms	4 MB
clang++-18	testcase_03	AC	5 ms	4 MB
clang++-18	testcase_04	AC	6 ms	4 MB
clang++-18	testcase_05	AC	5 ms	4 MB
clang++-18	testcase_06	AC	5 ms	4 MB
clang++-18	testcase_07	AC	5 ms	4 MB
clang++-18	testcase_08	AC	5 ms	4 MB
clang++-18	testcase_09	AC	5 ms	4 MB
clang++-18	testcase_10	AC	5 ms	4 MB
clang++-18	testcase_11	AC	5 ms	4 MB
clang++-18	testcase_12	AC	5 ms	4 MB
clang++-18	testcase_13	AC	5 ms	4 MB
clang++-18	testcase_14	AC	5 ms	4 MB
clang++-18	testcase_15	AC	6 ms	4 MB
clang++-18	testcase_16	AC	5 ms	4 MB
clang++-18	testcase_17	AC	6 ms	4 MB
clang++-18	testcase_18	AC	5 ms	4 MB
clang++-18	testcase_19	AC	6 ms	4 MB
clang++-18	testcase_20	AC	7 ms	4 MB