AtCoder Beginner Contest 442 E

https://atcoder.jp/contests/abc442/tasks/abc442_e

点を周方向に並べればよいです。+x軸上を一番大きいとして、反時計回りに小さくなっていくとします。集計するときは、+x軸をまたぐときは注意します。

// Laser Takahashi
#![allow(non_snake_case)]


//////////////////// library ////////////////////

fn read<T: std::str::FromStr>() -> T {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).ok();
    line.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace()
            .map(|e| e.parse().ok().unwrap()).collect()
}


//////////////////// Point ////////////////////

use std::cmp::Ordering;

#[derive(Debug, Eq, PartialEq, Copy, Clone)]
struct Point {
    X: i64,
    Y: i64
}

impl Ord for Point {
    fn cmp(&self, other: &Self) -> Ordering {
        if (self.Y >= 0) != (other.Y >= 0) {
            self.Y.cmp(&other.Y)
        }
        else if self.Y == 0 && other.Y == 0 {
            if (self.X > 0) == (other.X > 0) {
                Ordering::Equal
            }
            else {
                self.X.cmp(&other.Y)
            }
        }
        else {
            (self.X*other.Y - self.Y*other.X).cmp(&0)
        }
    }
}

impl PartialOrd for Point {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

impl Point {
    fn read() -> Self {
        let v: Vec<i64> = read_vec();
        let (X, Y) = (v[0], v[1]);
        Point { X, Y }
    }
}


//////////////////// SegTree ////////////////////

trait Monoid {
    type S: Clone;
    fn op(a: &Self::S, b: &Self::S) -> Self::S;
    fn e() -> Self::S;
}

struct SegTree<M: Monoid> {
    n: usize,
    size: usize,
    data: Vec<M::S>,
}

impl<M: Monoid> SegTree<M> {
    fn is_leaf(&self, i: usize) -> bool {
        i >= self.size - 1
    }
    
    fn new(n: usize) -> Self {
        let size = n.next_power_of_two();
        SegTree {
            n,
            size,
            data: vec![M::e(); size*2-1],
        }
    }
    
    fn from(v: Vec<M::S>) -> Self {
        let n = v.len();
        let size = n.next_power_of_two();
        let mut data = vec![M::e(); size*2-1];
        for i in 0..n {
            data[i+size-1] = v[i].clone();
        }
        let mut seg = SegTree { n, size, data };
        for i in (0..size-1).rev() {
            seg.data[i] = M::op(&seg.data[2*i+1], &seg.data[2*i+2]);
        }
        seg
    }
    
    fn set(&mut self, mut i: usize, x: M::S) {
        i = i + self.size - 1;
        self.data[i] = x;
        while i != 0 {
            i = (i - 1) / 2;
            self.data[i] = M::op(&self.data[2*i+1], &self.data[2*i+2]);
        }
    }
    
    fn prod(&self, mut l: usize, mut r: usize) -> M::S {
        let mut sml = M::e();
        let mut smr = M::e();
        l = l + self.size - 1;
        r = r + self.size - 1;
        while l < r {
            if l % 2 == 0 {
                sml = M::op(&sml, &self.data[l]);
                l += 1;
            }
            if r % 2 == 0 {
                r -= 1;
                smr = M::op(&self.data[r], &smr);
            }
            l = (l - 1) / 2;
            r = (r - 1) / 2
        }
        M::op(&sml, &smr)
    }
    
    fn get(&self, i: usize) -> M::S {
        self.data[i+self.size-1].clone()
    }
}


//////////////////// Monoid ////////////////////

struct Sum;
impl Monoid for Sum {
    type S = usize;     // 個数
    fn op(n1 : &Self::S, n2: &Self::S) -> Self::S {
        n1 + n2
    }
    fn e() -> Self::S { 0 }
}


//////////////////// Tree ////////////////////

struct Tree {
    seg: SegTree::<Sum>,
    ids: Vec<usize>     // 元のID -> 木でのID
}

impl Tree {
    fn size(&self) -> usize {
        self.seg.n
    }
    
    // 与えられたID以下の個数
    fn count(&self, A: usize, B: usize) -> usize {
        let i = self.ids[A];
        let j = self.ids[B];
        if i <= j {
            self.seg.prod(i, j+1)
        }
        else {
            self.seg.prod(i, self.size()) + self.seg.prod(0, j+1)
        }
    }
    
    fn create_ids(C: Vec<(usize, Point)>) -> Vec<usize> {
        // 同じ角度はまとめる
        let N = C.len();
        let mut ids: Vec<usize> = vec![0; N];
        let mut k: usize = 0;
        let mut prev_point: Point = C[0].1.clone();
        for (i, point) in C.into_iter() {
            if prev_point.cmp(&point) != Ordering::Equal {
                prev_point = point;
                k += 1
            }
            ids[i] = k
        }
        ids
    }
    
    fn from(points: Vec<Point>) -> Tree {
        let mut C: Vec<(usize, Point)> = points.into_iter().
                                            enumerate().collect();
        C.sort_by(|a, b| a.1.cmp(&b.1));
        let ids = Tree::create_ids(C);
        let M = ids.iter().max().unwrap() + 1;
        let mut a: Vec<usize> = vec![0; M];
        for &k in ids.iter() {
            a[k] += 1
        }
        let seg = SegTree::from(a);
        Tree { seg, ids }
    }
}


//////////////////// process ////////////////////

fn read_input() -> (usize, Vec<Point>) {
    let v: Vec<usize> = read_vec();
    let (N, Q) = (v[0], v[1]);
    let monsters: Vec<Point> = (0..N).map(|_| Point::read()).collect();
    (Q, monsters)
}

fn read_query() -> (usize, usize) {
    let v: Vec<usize> = read_vec();
    let (A, B) = (v[0]-1, v[1]-1);
    (A, B)
}

fn F(Q: usize, monsters: Vec<Point>) {
    let tree = Tree::from(monsters);
    for _ in 0..Q {
        let (A, B) = read_query();
        println!("{}", tree.count(A, B))
    }
}

fn main() {
    let (Q, monsters) = read_input();
    F(Q, monsters)
}