# Team Reference Materials

## Debug List

* Check Sample Input/Output **manually**
* Check integer overflow (no need in python)
* Check I/O format
* floating point -> int: unwanted ".0"?
* case-sensitive? ("YES" / "Yes" / "yes")
* Check if DFS too deep? (stack overflow)
* Check boundary and edge cases
* Missing Constraints?
* 1 second is roughly $10^8$ operations.
* $O(n)$ for $n\approx 2\times 10^6$
* $O(n\log n)$ for $n\approx 3\times 10^5$
* $O(n^2)$ for $n\approx 5000$
* $O(n^3)$ for $n\approx 500$
* $O(2^n)$ for $n\le 25$.

## Common Macros

# Faster input()
import sys
input = sys.stdin.readline

## Common Algorithms and Data Structures

### Union-Find Data Structure

class UnionFind:
  """ Elements have labels 1~n. 
  Tested on https://open.kattis.com/problems/unionfind
  """
  def __init__(self, n):
    self.n = n
    self.group = [i for i in range(0, n+1)]

  def find(self, x):
    path = [x]
    while self.group[path[-1]] != path[-1]:
      path.append(self.group[path[-1]])
    for elem in path:
      self.group[elem] = path[-1]
    return path[-1]

  def union(self, x, y):
    self.group[self.find(x)] = self.find(y)

### Binary Indexed Tree (Fenwick Tree)

class FenwickTree:
  """ Support index range 1 to N.
  Tested on https://open.kattis.com/problems/fenwick
  """
  def __init__(self, _N):
    self.N = _N + 1
    self.A = [0] * self.N
  
  def add(self, idx, val):
    # idx must be 1-index based.
    while idx < self.N:
      self.A[idx] += val
      idx += (idx & -idx)
    
  def prefix_sum(self, idx):
    ret = 0
    while idx > 0:
      ret += self.A[idx]
      idx -= (idx & -idx)
    return ret

## Math Formulas

### Trigonometric Equations

* $\cos(\alpha+\beta)= \cos\alpha\cos\beta -\sin\alpha\sin\beta$
* $\sin(\alpha+\beta)= \cos\alpha\sin\beta + \sin\alpha\cos\beta$

### Area of a Triangle

* Given coordinates: $\frac{1}{2}|x_Ay_B+x_By_C+x_Cy_A-x_By_A-x_Cy_B-x_Ay_C|$.
* Given side lengths: $s=\frac{a+b+c}{2}$; $\triangle ABC=\sqrt{s(s-a)(s-b)(s-c)}.$

### Area of a Polygon

Here $(x_{n+1}, y_{n+1})$ is defined to be $(x_1, y_1)$:
$$ \frac12\left| \sum_{i=1}^n (x_iy_{i+1}-x_{i+1}y_i) \right| $$