use std::io::{self, BufRead};
use std::collections::BTreeMap;

#[derive(Clone, Copy, Debug, PartialEq)]
struct Asteroid {
    x: f64,
    y: f64,
}

impl Asteroid {
    fn new(x: f64, y: f64) -> Asteroid {
        Asteroid {
            x,
            y,
        }
    }
}

#[derive(Clone, Copy, Debug)]
struct Pair<'a> {
    first: &'a Asteroid,
    second: &'a Asteroid,
}

type Asteroids = Vec<Asteroid>;

fn read_map() -> Asteroids {
    let mut asteroids: Asteroids = Vec::new();
    let stdin = io::stdin();

    for (y, line) in stdin.lock().lines().enumerate() {
        match line {
            Ok(s) => {
                for (x, byte) in s.as_bytes().iter().enumerate() {
                  if *byte == b'#' {
//                      println!("Asteroid found at {}, {}.", x, y);
                      asteroids.push(Asteroid::new(x as f64, y as f64));
                  }
                }
            },
            _ => eprintln!("Failed to parse input at row {}.", y),
        }
    }

    asteroids
}

fn calc_distance_angle(observer: &Asteroid, observee: &Asteroid) -> (f64, f64)
{
    let xdiff = observee.x - observer.x;
    let ydiff = observer.y - observee.y;

    let distance = f64::sqrt(xdiff.powf(2.0) + ydiff.powf(2.0));
    let mut angle = f64::atan2(xdiff,ydiff);
    if angle.is_sign_negative() {
        angle += std::f64::consts::PI*2.0;
    }

    (distance, angle)
}

fn float_encode(f: f64) -> i128 {
    (f * f64::powf(10.0, 37.0)) as i128
}

fn float_decode(i: i128) -> f64 {
    (i as f64 / i128::pow(10, 37) as f64)
}

fn main() {
    println!("Reading map");
    let asteroids = read_map();

    let mut angles = BTreeMap::new();
    println!("Calculating distances between all asteroids");
    for observer in &asteroids {
        for observee in &asteroids {
            if observer == observee { continue; }

            let ( distance, angle ) = calc_distance_angle(observer, observee);
            let dist_int = float_encode(distance);
            let ang_int = float_encode(angle);

            let pair = Pair {first: observer, second: observee};
            let distances:&mut BTreeMap<i128, Vec<Pair>> =
                angles.entry(ang_int).or_insert(BTreeMap::new());
            distances.entry(dist_int).or_insert(Vec::new()).push(pair);
        }
    }

    println!("Building huge angle and distance sorted datastructure of all asteroids.");
    let mut huge:Vec<Vec<(Asteroid, f64, f64, Asteroid)>> = asteroids.iter()
        .map(|asteroid| { let a:Vec<(Asteroid, f64, f64, Asteroid)> = angles.iter()
            .map(|(angle, distances)| {
                let a:Vec<(Asteroid, f64, f64, Asteroid)> = distances.iter()
                .map(|(distance, pairs)| pairs.iter()
                    .filter(|pair| if asteroid == pair.first {
                        true
                    } else {
                        false
                    })
                    .map(move |pair| { (
                        *asteroid,
                        float_decode(*angle),
                        float_decode(distance.clone()),
                        *pair.second
                    )})
                ).flatten().collect(); a
            }).flatten().collect() ; a
        }).collect();

    println!("Creating vector merely containing visible asteroids");
    let visible_asteroids:Vec<usize> = huge.iter()
        .map(|i| { let (_, n) = i.iter()
             .fold((std::f64::consts::PI*3.0, 0),
                  |( ang, res ), (_asteroid, angle, _distance, _other)|
             {
                 if f64::abs(ang - *angle) < 0.00000001 {
                     ( *angle, res )
                 } else {
                     ( *angle, res + 1)
             } }); n
        }
        ).collect();

    let highest_no_visible_asteroids = visible_asteroids.iter().max().unwrap();

    let mut best_asteroid = 0;
    for ( which, val ) in visible_asteroids.iter().enumerate() {
        if val == highest_no_visible_asteroids {
            best_asteroid = which;
        }
    }
    println!("Found out that {} other asteroids can be seen from the best asteroid.",
        visible_asteroids[best_asteroid]);

    let mut no_zapped = 0;
    let mut index = 0;
    let mut last_angle = -1.0;
    println!("Powering up lazer...");
    loop {
        if index >= huge[best_asteroid].len() {
            if index == 1 {
                eprintln!("Not enough asteroids to zap!");
                break;
            }
            index = 0;
        }

        let short = huge[best_asteroid][index];
        if short.1 != last_angle {
            let (_, angle, _, zapped_asteroid) = huge[best_asteroid].remove(index);
            last_angle = angle;
            no_zapped += 1;
            if no_zapped == 200 {
                println!("\rLast asteroid zapped was at {:?} {:?}",
                    zapped_asteroid.x, zapped_asteroid.y);
                break;
            }
        } else {
            index += 1;
        }
    }

}