pub mod minimum_bounding_circle {
pub fn make_circle(ps: &[Point<f64>]) -> (Point<f64>, f64) {
let n = ps.len();
assert!(n >= 2);
let mut c = make_circle2(ps[0], ps[1]);
for i in 2..n {
if is_included(ps[i], c) {
continue;
}
c = make_circle2(ps[0], ps[i]);
for j in 1..i {
if is_included(ps[j], c) {
continue;
}
c = make_circle2(ps[i], ps[j]);
for k in 0..j {
if is_included(ps[k], c) {
continue;
}
c = make_circle3(ps[i], ps[j], ps[k]);
}
}
}
c
}
fn make_circle3(a: Point<f64>, b: Point<f64>, c: Point<f64>) -> (Point<f64>, f64) {
let ea = (b - c).norm();
let eb = (c - a).norm();
let ec = (a - b).norm();
let s = (b - a).det(&(c - a));
let center = (a * ea * (eb + ec - ea) + b * eb * (ec + ea - eb) + c * ec * (ea + eb - ec))
/ (s * s * 4.0);
let r2 = (center - a).norm();
(center, r2)
}
fn make_circle2(a: Point<f64>, b: Point<f64>) -> (Point<f64>, f64) {
let c = (a + b) / 2.0;
let r2 = (a - c).norm();
(c, r2)
}
fn is_included(a: Point<f64>, circle: (Point<f64>, f64)) -> bool {
let (center, r2) = circle;
(a - center).norm() <= r2
}
pub struct Point<T> {
pub x: T,
pub y: T,
}
impl<T> Copy for Point<T> where T: Copy {}
impl<T> Clone for Point<T>
where
T: Clone,
{
fn clone(&self) -> Point<T> {
Point {
x: self.x.clone(),
y: self.y.clone(),
}
}
}
impl<T> std::ops::Sub for Point<T>
where
T: std::ops::Sub<Output = T>,
{
type Output = Point<T>;
fn sub(self, other: Point<T>) -> Point<T> {
Point {
x: self.x - other.x,
y: self.y - other.y,
}
}
}
impl<T> std::ops::Mul<T> for Point<T>
where
T: Copy + std::ops::Mul<Output = T>,
{
type Output = Point<T>;
fn mul(self, rhs: T) -> Point<T> {
Point {
x: self.x * rhs,
y: self.y * rhs,
}
}
}
impl<T> std::ops::Div<T> for Point<T>
where
T: Copy + std::ops::Div<Output = T>,
{
type Output = Point<T>;
fn div(self, rhs: T) -> Point<T> {
Point {
x: self.x / rhs,
y: self.y / rhs,
}
}
}
impl<T> std::ops::Add<Point<T>> for Point<T>
where
T: std::ops::Add<Output = T>,
{
type Output = Point<T>;
fn add(self, rhs: Point<T>) -> Point<T> {
Point {
x: self.x + rhs.x,
y: self.y + rhs.y,
}
}
}
impl<T> Point<T>
where
T: Copy + std::ops::Mul<Output = T> + std::ops::Sub<Output = T> + std::ops::Add<Output = T>,
{
pub fn det(&self, other: &Point<T>) -> T {
self.x * other.y - self.y * other.x
}
pub fn norm(&self) -> T {
self.x * self.x + self.y * self.y
}
}
}
#[cfg(test)]
mod tests {
use super::minimum_bounding_circle::*;
use crate::utils::test_helper::Tester;
#[test]
fn solve_aoj2423() {
let tester = Tester::new("./assets/AOJ2423/in/", "./assets/AOJ2423/out/");
tester.test_solution(|sc| {
let circles: usize = sc.read();
let people: usize = sc.read();
let rs: Vec<f64> = sc.vec(circles);
let mut people_r2 = vec![0.0; people];
let mut people_list = vec![];
for i in 0..people {
let n: usize = sc.read();
let mut ps = vec![];
for _ in 0..n {
let x: f64 = sc.read();
let y: f64 = sc.read();
ps.push(Point { x, y });
}
let (_, r2) = make_circle(&ps);
people_list.push((r2, i));
people_r2[i] = r2;
}
let mut circle_list = rs
.iter()
.enumerate()
.map(|(i, &r)| (r, i))
.collect::<Vec<_>>();
circle_list.sort_by(|a, b| a.0.partial_cmp(&b.0).unwrap());
people_list.sort_by(|a, b| a.0.partial_cmp(&b.0).unwrap());
let mut ans = vec![0; people];
for _ in 0..people {
let mut circle_buf = 0;
let mut people_buf = people_list.len();
for p_pos in (0..people_list.len()).rev() {
for c_pos in (0..(circle_list.len() - circle_buf)).rev() {
if circle_list[c_pos].0 * circle_list[c_pos].0 >= people_list[p_pos].0 {
circle_buf += 1;
} else {
break;
}
}
if people_list.len() - p_pos > circle_buf {
sc.write("NG\n");
return;
} else if people_list.len() - p_pos == circle_buf {
people_buf = people_list.len() - p_pos;
break;
}
}
let youngest_people = people_list
.iter()
.rev()
.take(people_buf)
.map(|p| p.1)
.min()
.unwrap();
let youngest_circle = circle_list
.iter()
.rev()
.take(circle_buf)
.map(|c| c.1)
.filter(|&i| rs[i] * rs[i] >= people_r2[youngest_people])
.min()
.unwrap();
ans[youngest_people] = youngest_circle;
people_list = people_list
.into_iter()
.filter(|p| p.1 != youngest_people)
.collect::<Vec<_>>();
circle_list = circle_list
.into_iter()
.filter(|c| c.1 != youngest_circle)
.collect::<Vec<_>>();
}
for i in ans.into_iter() {
sc.write(format!("{}\n", i + 1));
}
});
}
}