jacky860226

using Point = pair<int,int>;
ll cross(const Point& a, const Point& b) {
    return 1ll * a.first * b.second - 1ll * a.second * b.first;
}
// 逆时针
// 参考 mnbvmar 的写法：https://codeforces.com/contest/1284/submission/68178688
bool cmp_polar(const Point& a, const Point& b) {
    bool aorig = a.second > 0;
    bool borig = b.second > 0;
    if (aorig != borig) {

jacky860226

using LL = long long;
auto garner(const std::vector<LL> &A, const std::vector<LL> &M, LL mod) {
    assert(A.size() == M.size());
    auto X = A;
    for (size_t i = 0; i < A.size(); ++i) {
        for (size_t j = 0; j < i; ++j) {
            X[i] = mod_inv(M[j], M[i]) * (X[i] - X[j]) % M[i];
            if (X[i] < 0) X[i] += M[i];
        }
    }

jacky860226

#include <algorithm>
#include <cassert>
#include <cstddef>
template <typename T, typename Policy>
class CooleyTukeyAlgorithm {
    size_t reverse_bits_len(size_t N, size_t len) {
        return ::reverse_bits(N) >> (sizeof(N) * 8 - len);
    }

   public:

jacky860226

template <class ValueTy> struct Tree {
  int L, R;
  Tree *lc, *rc;
  ValueTy Val;
  Tree() = default;
  Tree(int L, int R) : L(L), R(R), lc(nullptr), rc(nullptr), Val() {}
  void pull() {
    Val = 0;
    if (lc)
      Val += lc->Val;

jacky860226

#include <bits/stdc++.h>
using namespace std;

namespace system_test {

const size_t KB = 1024;
const size_t MB = KB * 1024;
const size_t GB = MB * 1024;

size_t block_size, bound;

jacky860226

#include <algorithm>
#include <stdexcept>
#include <vector>
template <typename T, typename Alloc = std::allocator<T>>
class Discretizer : private std::vector<T, Alloc> {
  void build() {
    std::sort(std::vector<T, Alloc>::begin(), std::vector<T, Alloc>::end());
    std::vector<T, Alloc>::erase(std::unique(std::vector<T, Alloc>::begin(),
                                             std::vector<T, Alloc>::end()),
                                 std::vector<T, Alloc>::end());

jacky860226

// https://en.wikipedia.org/wiki/Recursive_descent_parser

#include <bits/stdc++.h>

/// Conditional const
/// cond_const<true,  Type>: const Type
/// cond_const<false, Type>: Type
template <bool Const, class Type> struct cond_const {
  typedef const Type type;
  typedef const Type *ptr;

jacky860226

template <typename T> struct point {
  T x, y;
  point() {}
  point(const T &x, const T &y) : x(x), y(y) {}
  point operator+(const point &b) const { return point(x + b.x, y + b.y); }
  point operator-(const point &b) const { return point(x - b.x, y - b.y); }
  point operator*(const T &b) const { return point(x * b, y * b); }
  bool operator==(const point &b) const { return x == b.x && y == b.y; }
  T dot(const point &b) const { return x * b.x + y * b.y; }
  T cross(const point &b) const { return x * b.y - y * b.x; }

jacky860226

import copy
import pygame,sys,time,random
from pygame.locals import *
class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y
    def __eq__(self, other):
        return self.x==other.x and self.y==other.y

jacky860226

template<typename T>
class kruskal{
	static const int MAXN=100005;
	int n; // 1-base
	tuple<T,int,int> edge;
	int pa[MAXN];
	int find(int x){
		if(x==pa[x]) return x;
		return pa[x] = find(pa[x]);
	}