




## 整体二分

整体二分的基本思想是，二分出一个 $mid$，然后遍历所有的询问，每个询问都 check 一下 mid 是偏大了还是偏小了。把偏大的询问分成一组，偏小的询问分成另一组。然后这两组询问再分别二分

### P3332 [ZJOI2013] K大数查询

https://www.luogu.com.cn/problem/P3332

**题目描述**

你需要维护 $n$ 个可重整数集，集合的编号从 $1$ 到 $n$。  

这些集合初始都是空集，有 $m$ 个操作：  

- `1 l r c`：表示将 $c$ 加入到编号在 $[l,r]$ 内的集合中  
- `2 l r c`：表示查询编号在 $[l,r]$ 内的集合的并集中，第 $c$ 大的数是多少。  

注意可重集的并是不去除重复元素的，如 $\{1,1,4\}\cup\{5,1,4\}=\{1,1,4,5,1,4\}$。

**数据范围**

$1 \le n,m \le 5\times 10^4$ 

$1\le l,r \le n$ 

$1$ 操作中 $|c|\le n$ 

$2$ 操作中 $1\le c   2^{63}$，第 $c$ 大的数存在

**笔记**

```cpp
#include bits/stdc++.h 
#define int long long
#define ull unsigned long long
#define ls(k) (k)  1
#define rs(k) (k)  1|1
#define debug(x) cout  #x  "="  x  endl
using namespace std;
const int inf=0x3f3f3f3f3f3f3f3f;
const int mod=0;
typedef pair int,int  pii;
#define _ 50004
int n,arr[_],m,sum[_  2],tag[_  2];
inline void pushup(int k){sum[k]=sum[ls(k)]+sum[rs(k)];}
inline void pushadd(int k,int l,int r,int v){sum[k]+=v*(r-l+1),tag[k]+=v;}
inline void pushdown(int k,int l,int r,int mid){if(tag[k])pushadd(ls(k),l,mid,tag[k]),pushadd(rs(k),mid+1,r,tag[k]),tag[k]=0;}
void modify(int k,int l,int r,int x,int y,int v){
    if(l =x  r =y) return pushadd(k,l,r,v),void();
    int mid=(l+r)  1;
    pushdown(k,l,r,mid);
    if(x =mid) modify(ls(k),l,mid,x,y,v);
    if(y mid) modify(rs(k),mid+1,r,x,y,v);
    pushup(k);
}
int query(int k,int l,int r,int x,int y){
    if(l =x  r =y) return sum[k];
    int mid=(l+r)  1,res=0;
    pushdown(k,l,r,mid);
    if(x =mid) res+=query(ls(k),l,mid,x,y);
    if(y mid) res+=query(rs(k),mid+1,r,x,y);
    return res;
}
struct Q{int l,r,x,id,ans,op;} L[_],R[_],q[_];
void solve(int l,int r,int ql,int qr){
    if(ql qr) return;
    if(l==r){
        for(int i=ql;i =qr;i++) if(q[i].op==2) q[i].ans=l;
        return;
    }
    int mid=(l+r)  1;
    int cntl=0,cntr=0;
    for(int i=ql;i =qr;i++){
        if(q[i].op==1){
            if(q[i].x mid) modify(1,1,n,q[i].l,q[i].r,1),R[++cntr]=q[i];
            else L[++cntl]=q[i];
        }else{
            int cnt=query(1,1,n,q[i].l,q[i].r);
            if(q[i].x =cnt) R[++cntr]=q[i];
            else q[i].x-=cnt,L[++cntl]=q[i];
        }
    }
    for(int i=ql;i =qr;i++) if(q[i].op==1  q[i].x mid) modify(1,1,n,q[i].l,q[i].r,-1);
    for(int i=1;i =cntl;i++) q[ql-1+i]=L[i];
    for(int i=1;i =cntr;i++) q[ql+cntl-1+i]=R[i];
    solve(l,mid,ql,ql+cntl-1);
    solve(mid+1,r,ql+cntl,qr);
}
inline void subtask(){
    cin  n  m;
    for(int i=1;i =m;i++) cin  q[i].op  q[i].l  q[i].r  q[i].x,q[i].id=i;
    solve(-n,n,1,m);
    sort(q+1,q+m+1,[](Q x,Q y){return x.id y.id;});
    for(int i=1;i =m;i++) if(q[i].op==2) cout  q[i].ans  endl;
}
signed main(){
    ios::sync_with_stdio(false);
    int t=1;//cin  t;
    while(t--) subtask();
    return 0;
}
```

因为我们判断 mid 是偏大了还是偏小了，需要知道比 mid 大的数有多少，因此我们把大于 $mid$ 的 $x$ 值加入线段树。并且，如果询问需要归到 $R$ 中，那么也只有 $x$ 值大于 $mid$ 的操作一会影响到这些询问，因此 $x$ 值大于 $mid$ 的操作也归到 $R$ 中

### P3527 [POI 2011] MET-Meteors

https://www.luogu.com.cn/problem/P3527

**题目描述**

有 $n$ 个成员国。现在它发现了一颗新的星球，这颗星球的轨道被分为 $m$ 份（第 $m$ 份和第 $1$ 份相邻），第 $i$ 份上有第 $a_i$ 个国家的太空站。

这个星球经常会下陨石雨。BIU 已经预测了接下来 $k$ 场陨石雨的情况。

BIU 的第 $i$ 个成员国希望能够收集 $p_i$ 单位的陨石样本。你的任务是判断对于每个国家，它需要在第几次陨石雨之后，才能收集足够的陨石。

**输入格式**

第一行是两个数 $n,m$。

第二行有 $m$ 个数，第 $i$ 个数 $o_i$ 表示第 $i$ 段轨道上有第 $o_i$ 个国家的太空站。

第三行有 $n$ 个数，第 $i$ 个数 $p_i$ 表示第 $i$ 个国家希望收集的陨石数量。

第四行有一个数 $k$，表示 BIU 预测了接下来的 $k$ 场陨石雨。 接下来 $k$ 行，每行有三个数 $l_i,r_i,a_i$ ，表示第 $k$ 场陨石雨的发生地点在从 $l_i$ 顺时针到 $r_i$ 的区间中（如果 $l_i \leq r_i$，则是 $l_i, l_i + 1 
\cdots, r_i$，否则就是 $l_i, l_i + 1, 
\cdots m - 1, m, 1, 2, \cdots r_i$），向区间中的每个太空站提供 $a_i$ 单位的陨石样本。

**数据范围**

$1\le n,m,k\le 3\cdot10^5$；

$1\le p_i,a_i\le 10^9$；

**笔记**

把环形的区间加拆成两个操作，然后整体二分即可。整体二分时直接暴力计算每个询问是否满足要求貌似是可以的

```cpp
#include bits/stdc++.h 
#define int long long
#define ull unsigned long long
#define ls(k) (k)  1
#define rs(k) (k)  1|1
#define debug(x) cout  #x  "="  x  endl
using namespace std;
const int inf=0x3f3f3f3f3f3f3f3f;
const int mod=0;
typedef pair int,int  pii;
#define _ 900005
int arr[_],n,m;
inline int lowbit(int x){return x -x;}
inline void modify(int x,int v){while(x =m) arr[x]+=v,x+=lowbit(x);}
inline int query(int x,int res=0){while(x) res+=arr[x],x-=lowbit(x);return res;}
struct Q{int l,r,id,ans,op,x,need;} q[_],L[_],R[_];
vector int  g[_];
void solve(int l,int r,int ql,int qr){
    if(ql qr) return;
    if(l==r){
        for(int i=ql;i =qr;i++) if(q[i].op==0) q[i].ans=l;
        return;
    }
    int mid=(l+r)  1,cntl=0,cntr=0;
    for(int i=ql;i =qr;i++){
        if(q[i].op==1){
            if(q[i].id =mid) modify(q[i].l,q[i].x),modify(q[i].r+1,-q[i].x),L[++cntl]=q[i];
            else R[++cntr]=q[i];
        }else{
            int s=0;
            for(auto to:g[q[i].x]){
                s+=query(to);
                if(s =q[i].need) break;
            }
            if(s =q[i].need) L[++cntl]=q[i];
            else q[i].need-=s,R[++cntr]=q[i];
        }
    }
    for(int i=ql;i =qr;i++) if(q[i].op==1  q[i].id =mid) modify(q[i].l,-q[i].x),modify(q[i].r+1,q[i].x);
    for(int i=1;i =cntl;i++) q[ql+i-1]=L[i];
    for(int i=1;i =cntr;i++) q[ql+cntl+i-1]=R[i];
    solve(l,mid,ql,ql+cntl-1);
    solve(mid+1,r,ql+cntl,qr);
}
int need[_];
inline void subtask(){
    cin  n  m;
    for(int i=1,x;i =m;i++) cin  x,g[x].push_back(i);
    for(int i=1;i =n;i++) cin  need[i];
    int totq,cntq=0;cin  totq;
    for(int i=1;i =totq;i++){
        int l,r,x;cin  l  r  x;
        if(l =r) q[++cntq].l=l,q[cntq].r=r,q[cntq].op=1,q[cntq].id=i,q[cntq].x=x;
        else q[++cntq].l=1,q[cntq].r=r,q[cntq].op=1,q[cntq].id=i,q[cntq].x=x,q[++cntq].l=l,q[cntq].r=m,q[cntq].op=1,q[cntq].id=i,q[cntq].x=x;
    }
    for(int i=1;i =n;i++) q[++cntq].id=i,q[cntq].x=i,q[cntq].need=need[i];
    //for(int i=1;i =cntq;i++) debug(q[i].op),debug(q[i].l),debug(q[i].r);
    solve(1,totq+1,1,cntq);
    sort(q+1,q+cntq+1,[](Q x,Q y){return x.id y.id;});
    for(int i=1;i =cntq;i++){
        if(q[i].op) continue;
        if(q[i].ans==totq+1) cout  "NIE"  endl;
        else cout  q[i].ans  endl;
    }
}
signed main(){
    ios::sync_with_stdio(false);
    int t=1;//cin  t;
    while(t--) subtask();
    return 0;
}
```









## 基础

### 圆周率

```cpp
const double pi=acos(-1);
```

### 偏差值

```cpp
const double eps=1e-8;
```

一般取 1e-8，再小可能就出问题了

### 符号函数

```cpp
inline int sgn(double x){return fabs(x) =eps?0:(x 0?1:-1);}
```

### 浮点数输出

当输出浮点数的 0 时，可能会出现输出了 `-0.00000...` 的情况，某些题目中需要特判：

```cpp
inline double fit(double x){return sgn(x)==0?0:x;}
```

### 精度问题

1. 能整数解决的问题就不要使用浮点数。同时注意，如果运算过程中都是整数，但还是用double类型，还是会发生精度损失
2. 使用 long double 减少精度损失
3. 把所有数放大 1000 倍减少精度损失

## 点

### 表示

```cpp
struct Point{
    double x,y;
    Point(){}
    Point(double x,double y):x(x),y(y){}
};
```

### 两点距离公式

```cpp
inline double dis(Point a,Point b){return hypot(a.x-b.x,a.y-b.y);}
```

### 判等

```cpp
bool operator==(Point b){return sgn(x-b.x)==0  sgn(y-b.y)==0;}
```

## 向量

### 表示

可以直接用点来表示向量。把所有向量视为起点为原点

```cpp
typedef Point Vector;
```

### 向量运算

```cpp
Point operator+(Point b){return Point(x+b.x,y+b.y);}
Point operator-(Point b){return Point(x-b.x,y-b.y);}
Point operator*(double k){return Point(x*k,y*k);}
Point operator/(double b){return Point(x/k,y/k);}
```

### 点积

```cpp
double operator*(Point b){return x*b.x+y*b.y;}
```

#### 求向量模长

```cpp
inline double len(Point a){return sqrt(a*a);}
```

有时开方会损失精度，可以改为求长度的平方

```cpp
inline double len2(Point a){return a*a;}
```

#### 夹角

返回的是 cos 值

```cpp
inline double angle(Point a,Point b){return a*b/len(a)/len(b);}
```

### 叉积

```cpp
double operator^(Point b){return x*b.y-y*b.x;}
```

#### 面积

以 a 为 公共点，b 到 c 的有向面积

```cpp
inline double area(Point a,Point b,Point c){return (b-a)^(c-a);}
```

#### 向量旋转与法向量

向量 $(x,y)$ 绕原点逆时针旋转度数 $\theta$，得到向量 $(x',y')$，有如下关系：
$$
x'=x \cos \theta - y \sin \theta \\
y'=x \sin \theta + y \cos \theta
$$

```cpp
inline Point rotate(Point a,double rad){return Point(a.x*cos(rad)-a.y*sin(rad),a.x*sin(rad)+a.y*cos(rad));}
```

法向量为向量逆时针旋转 $90^{\circ} $

```cpp
inline Point normal(Point a){return Point(-a.y/len(a),a.x/len(a));}
```

## 线

### 表示

```cpp
struct Line{
    Point s,t;
    Line(){}
    Line(Point s,Point t):s(s),t(t){}
};
```

### 斜率

```cpp
inline double slope(Point a,Point b){return (a.y-b.y)/(a.x-b.x);}
```

### 倾斜角

```cpp
inline double angle(Line l){
    double k=atan2(l.s.y-l.t.y,l.s.x-l.t.x);
    if(sgn(k) 0) k+=pi;
    if(sgn(k-pi)==0) k=pi;
    return k;
}
```

### 点与线

#### 点与直线位置

点在直线左边还是右边需要看你是从直线哪个方向观察的，这里传递的线段应视为有向线段，从 s 指向 t

```cpp
inline int plr(Point p,Line l){//0:on -1:left 1:right
    int k=sgn((l.t-l.s)^(p-l.s));
    if(k 0) return -1;
    if(k 0) return 1;
    return 0;
}
```

#### 点是否在线段上

先用叉积判断是否共线，再用点积判断是否在线段上

```cpp
inline bool on_seg(Point p,Line l){return plr(p,l)==0  sgn((p-l.s)*(p-l.t)) =0;}
```

#### 点到直线距离

先叉积求出构成的平行四边形面积，然后面积除以底就得到了高，即点到直线距离

```cpp
inline double dis(Point p,Line l){return fabs((p-l.s)^(l.s-l.t)/dis(l.s,l.t));}
```

#### 点在直线上投影

```cpp
inline Point proj(Point p,Line l){return l.s+(l.t-l.s)*(l.t-l.s)*(p-l.s)/len2(l.t-l.s);}
```

#### 点关于直线对称

```cpp
inline Point symmetry(Point p,Line l){return 2*proj(p,l)-p;}
```

#### 点到线段距离

过点向线段所在直线作垂线，如果垂足落在线段上，那么点到线段的距离为点到直线距离，反之，则为点到线段两端点的最小值

```cpp
inline double dis_seg(Point p,Line l){
    if(sgn((p-l.s)*(l.t-l.s)) 0||sgn((p-l.t)*(l.s-l.t)) 0) return min(dis(p,l.s),dis(p,l.t));
    return dis(p,l);
}
```

### 线与线

#### 两直线位置关系

平行、重合、相交

```cpp
inline int llr(Line l1,Line l2){//0:平行 1:相交 2:重合
    if(sgn((l1.s-l1.t)^(l2.s-l2.t))==0){
        if(plr(l1.s,l2)==0) return 2;
        else return 0;
    }
    return 1;
}
```

#### 两线段位置关系

返回值如下：

0. 不相交
1. 非规范相交：交点在端点上
2. 规范相交：交点在线段内部

```cpp
inline int ssr(Line l1,Line l2){//0:不相交 1:非规范相交 2:规范相交
    int c1=plr(l1.s,l2),c2=plr(l1.t,l2);
    int d1=plr(l2.s,l1),d2=plr(l2.t,l1);
    if(c1*c2 0  d1*d2 0) return 2;
    return (c1==0  on_seg(l1.s,l2))||(c2==0  on_seg(l1.t,l2))||(d1==0  on_seg(l2.s,l1))||(d2==0  on_seg(l2.t,l1));
}
```

#### 线段和直线关系

返回值：

0. 不相交

1. 非规范相交
2. 规范相交
3. 重合

```cpp
inline int slr(Line s,Line l){//0:不相交 1:非规范相交 2:规范相交 3:重合
    int d1=plr(s.s,l),d2=plr(s.t,l);
    if(d1==0  d2==0) return 3;
    if(d1*d2==0) return 1;
    if(d1*d2 0) return 2;
    return 0;
}
```

#### 两直线交点

调用该函数前应确保两条直线存在交点

```cpp
inline Point cp(Line l1,Line l2){
    double s1=(l1.t-l1.s)^(l2.s-l1.s);
    double s2=(l1.t-l1.s)^(l2.t-l1.s);
    return (l2.s*s2-l2.t*s1)/(s2-s1);
}
```

#### 线段与线段距离

设 $P_0$ 和 $P_1$ 构成线段 $L_1$，$P_2$ 和 $P_3$ 构成线段 $L_2$，则 $L_1$ 和 $L_2$ 的距离为：

* 如果 $L_1$ 和 $L_2$ 相交，则为 0
* 反之，则为 $P_0$ 到 $L_2$ ，$P_1$ 到 $L_2$，$P_2$ 到 $L_1$，$P_3$ 到 $L_1$ ，四者距离的最小值

## 基础点线模板汇总

```cpp
const double pi=acos(-1);
const double eps=1e-8;
inline int sgn(double x){return fabs(x) =eps?0:(x 0?1:-1);}
inline double fit(double x){return sgn(x)==0?0:x;}
struct Point{
    double x,y;
    Point(){}
    Point(double x,double 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*(double k) const {return Point(x * k, y * k);}
    double operator*(const Point  b) const {return x * b.x + y * b.y;}
    Point operator/(double k) const {return Point(x / k, y / k);}
    double operator^(const Point  b) const {return x * b.y - y * b.x;}
};
typedef Point Vector;
struct Line{
    Point s,t;
    Line(){}
    Line(Point s,Point t):s(s),t(t){}
};
inline double dis(Point a,Point b){return hypot(a.x-b.x,a.y-b.y);}
inline double dis(Point p,Line l){return fabs((p-l.s)^(l.s-l.t)/dis(l.s,l.t));}
inline double len(Point a){return sqrt(a*a);}
inline double len2(Point a){return a*a;}
inline double slope(Point a,Point b){return (a.y-b.y)/(a.x-b.x);}
inline double angle(Point a,Point b){return a*b/len(a)/len(b);}
inline double angle(Line l){
    double k=atan2(l.s.y-l.t.y,l.s.x-l.t.x);
    if(sgn(k) 0) k+=pi;
    if(sgn(k-pi)==0) k=pi;
    return k;
}
inline double area(Point a,Point b,Point c){return (b-a)^(c-a);}//a为公共点，b到c有向面积
inline Point rotate(Point a,double rad){return Point(a.x*cos(rad)-a.y*sin(rad),a.x*sin(rad)+a.y*cos(rad));}
inline Point normal(Point a){return Point(-a.y/len(a),a.x/len(a));}//逆时针旋转90度的法向量
inline int plr(Point p,Line l){//0:on -1:left 1:right
    int k=sgn((l.t-l.s)^(p-l.s));
    if(k 0) return -1;
    if(k 0) return 1;
    return 0;
}
inline bool on_seg(Point p,Line l){return plr(p,l)==0  sgn((p-l.s)*(p-l.t)) =0;}
inline Point proj(Point p,Line l){return l.s+(l.t-l.s)*((l.t-l.s)*(p-l.s))/len2(l.t-l.s);}
inline Point symmetry(Point p,Line l){return proj(p,l)*2-p;}
inline double dis_seg(Point p,Line l){
    if(sgn((p-l.s)*(l.t-l.s)) 0||sgn((p-l.t)*(l.s-l.t)) 0) return min(dis(p,l.s),dis(p,l.t));
    return dis(p,l);
}
inline int llr(Line l1,Line l2){//0:平行 1:相交 2:重合
    if(sgn((l1.s-l1.t)^(l2.s-l2.t))==0){
        if(plr(l1.s,l2)==0) return 2;
        else return 0;
    }
    return 1;
}
inline int ssr(Line l1,Line l2){//0:不相交 1:非规范相交 2:规范相交
    int c1=plr(l1.s,l2),c2=plr(l1.t,l2);
    int d1=plr(l2.s,l1),d2=plr(l2.t,l1);
    if(c1*c2 0  d1*d2 0) return 2;
    return (c1==0  on_seg(l1.s,l2))||(c2==0  on_seg(l1.t,l2))||(d1==0  on_seg(l2.s,l1))||(d2==0  on_seg(l2.t,l1));
}
inline int slr(Line s,Line l){//0:不相交 1:非规范相交 2:规范相交 3:重合
    int d1=plr(s.s,l),d2=plr(s.t,l);
    if(d1==0  d2==0) return 3;
    if(d1*d2==0) return 1;
    if(d1*d2 0) return 2;
    return 0;
}
inline Point cp(Line l1,Line l2){
    double s1=(l1.t-l1.s)^(l2.s-l1.s);
    double s2=(l1.t-l1.s)^(l2.t-l1.s);
    return (l2.s*s2-l2.t*s1)/(s2-s1);
}
```

## 多边形

### 表示

一般用下标从 0 开始的 Point 数组表示

### 多边形面积

```cpp
inline double area(Point *pg,int n){
    double res=0;
    for(int i=0;i n;i++) res+=area(Point(0,0),pg[i],pg[(i+1)%n])/2;
    return res;
}
```

### 多边形重心

将多边形三角剖分，计算出每个三角形的重心，然后再以三角形有向面积为权重加权平均

```cpp
inline Point polygon_center(Point *pg,int n){
    Point ans(0,0);
    if(area(pg,n)==0) return ans;
    for(int i=0;i n;i++) ans=ans+(pg[i]+pg[(i+1)%n])*area(Point(0,0),pg[i],pg[(i+1)%n]);
    return ans/area(pg,n)/6;
}
```

### 极角序

三四象限的点极角序最小，排序后是从三四象限的点（如果有）逆时针排序

代码是以原点为基点求的极角序，如果要以其他的点为基点，则需要把所有的点都减去那个基点

```cpp
inline bool pcmp(Point a,Point b){
    auto f=[](Point p){return p.y 0||(p.y==0  p.x 0);};
    if(f(a)!=f(b)) return f(a) f(b);
    else if((a^b)==0) return a.x b.x;
    else return (a^b) 0;
}
```

### 凸包

```cpp
inline int convex_hull(Point *pg,int n,Point *ch){//会将pg排序并去重，返回凸包顶点数，求的的凸包的点均为顶点，不存在两条边共线
    sort(pg,pg+n,[](Point a,Point b){
        if(sgn(a.x-b.x)==0) return sgn(a.y-b.y) 0;
        return sgn(a.x-b.x) 0;
    });
    n=unique(pg,pg+n)-pg;
    int cnt=0;
    for(int i=0;i n;i++){
        while(cnt =2  sgn((ch[cnt-1]-ch[cnt-2])^(pg[i]-ch[cnt-1])) =0) cnt--;
        ch[cnt++]=pg[i];
    }
    int t=cnt;
    for(int i=n-2;i =0;i--){
        while(cnt =t+1  sgn((ch[cnt-1]-ch[cnt-2])^(pg[i]-ch[cnt-1])) =0) cnt--;
        ch[cnt++]=pg[i];
    }
    if(n =2) cnt--;
    return cnt;
}
```

### 点在多边形内

#### 射线法

适用于任意多边形。具体原理是从要判断的点水平作射线，穿过了奇数条边则说明在多边形内部，反之则在多边形外部

但有几个特殊情况：如果遇到一个水平的边，则应视为没有穿过边；穿过了两条边交界处，应视为穿过了一个边；穿过了两条边构成的一个角的顶点，则应视为没有穿过边。其中前一种可以特判，后一种可以采取把线段看成上闭下开的形式来解决

```cpp
inline bool in_polygon(Point p,Point *pg,int n){// pg下标从0开始，在边上也算
    int ans=0;
    Point p1,p2;
    p1=pg[0];
    for(int i=1;i =n;i++){
        p2=pg[i%n];
        if(on_seg(p,Line(p1,p2))) return true;
        if(p1.y==p2.y){// 水平边不考虑
            p1=p2;
            continue;
        }
        if(p.y min(p1.y,p2.y)    p.y =max(p1.y,p2.y)    p.x =max(p1.x,p2.x)){//上取下不取
            if(p1.x==p2.x) ans++;
            else{
                double x=p1.x+(p.y-p1.y)/slope(p1,p2);
                if(p.x =x) ans++;
            }
        }
        p1=p2;
    }
    return ans 1;
}
```

时间复杂度 $O(n)$

#### 叉乘判断

只适用于判断点是否在凸包内

逐个计算点到凸包顶点构成的向量之间的叉乘是否是同号，即判断这些向量是否都往一个方向转，是的话就说明点在该凸包内

![](https://pic.caiwen.work/i/2025/02/18/67b46f833d5ba.png)

时间复杂度 $O(n)$

#### 二分法

只适用于凸包

首先把多边形划分为多个区域

![](https://pic.caiwen.work/i/2025/02/18/67b4701ee315a.png)

![](https://pic.caiwen.work/i/2025/02/18/67b470cc6b966.png)

如果要判断一个点是否在该凸包内，则先找到这个点在哪个区域内。如果不在这几个区域中，则必不在凸包内，否则我们只需要判断这个点和凸包的边的关系即可

![](https://pic.caiwen.work/i/2025/02/18/67b470e7ee9a7.png)

时间复杂度 $O(\log n)$

```cpp
int n,m,k,ok=0,cnt=1;cin  n  m  k;
for(int i=0;i n;i++) cin  p[i].x  p[i].y;
n=convex_hull(p,n,ch);
Point base=p[0];
for(int i=0;i n;i++) ch[i]=ch[i]-base;
while(m--){
    Point now;cin  now.x  now.y;
    now=now-base;
    if(plr(now,Line(ch[0],ch[1]))==0||plr(now,Line(ch[0],ch[n-1]))==0){
        if(on_seg(now,Line(ch[0],ch[1]))||on_seg(now,Line(ch[0],ch[n-1]))) ok++;
        continue;
    }
    if(!(plr(now,Line(ch[0],ch[1]))==-1  plr(now,Line(ch[0],ch[n-1]))==1)) continue;
    int l=1,r=n-1,ans=-1;
    while(l =r){
        int mid=(l+r)  1;
        if((ch[mid]^now) =0) ans=mid,l=mid+1;
        else r=mid-1;
    }
    if(ans==-1||ans==n-1) continue;
    if(plr(now,Line(ch[ans],ch[ans+1]))!=1) ok++;
}
if(ok =k) cout  "YES"  endl;
else cout  "NO"  endl;
```

## 其他

### 平面最近点对

```cpp
Point p[_];
int tmp[_];
double solve(int l,int r){
    if(l==r) return inf;
    if(l+1==r) return dis(p[l],p[r]);
    int mid=(l+r)  1,cnt=0;
    double d1=solve(l,mid),d2=solve(mid+1,r),d=min(d1,d2);
    for(int i=l;i =r;i++) if(fabs(p[mid].x-p[i].x) d) tmp[++cnt]=i;
    for(int i=1;i =cnt;i++){
        for(int j=1;j i;j++){
            double d3=dis(p[tmp[i]],p[tmp[j]]);
            d=min(d,d3);
        }
    }
    return d;
}
inline void subtask(){
    int n;cin  n;
    for(int i=1;i =n;i++) cin  p[i].x  p[i].y;
    sort(p+1,p+n+1,[](Point a,Point b){return sgn(a.x-b.x)==0? sgn(a.y-b.y) 0:sgn(a.x-b.x) 0;});
    double res=solve(1,n);
    printf("%.4lf",res);
}
```









## GSS1 - Can you answer these queries I

线段树

https://www.luogu.com.cn/problem/SP1043

**题目描述**

给 $n$ 个数字，$m$ 个询问，每次询问给定区间的最大字段和，$1\le n,m\le 5\times 10^4$

**笔记**

一上来口胡了个分治做法，用主定理分析了一下发现时间复杂度好像是 $O(mn\log n)$ 的（）

实际上维护区间前缀和最大值、后缀和的最大值、区间和、区间内最大字段和就好了

```cpp
#include bits/stdc++.h 
#define int long long
#define ull unsigned long long
#define ls(k) (k)  1
#define rs(k) (k)  1|1
#define nt tree[k]
#define lt tree[ls(k)]
#define rt tree[rs(k)]
#define debug(x) cout  #x  "="  x  endl
using namespace std;
const int inf=0x3f3f3f3f3f3f3f3f;
const int mod=0;
typedef pair int,int  pii;
#define _ 50004
int in[_],n,m;
struct Node{int lmax,rmax,sum,seg;} tree[_  2];
inline Node merge(Node l,Node r){
    Node res;
    res.sum=l.sum+r.sum;
    res.lmax=max(l.lmax,l.sum+r.lmax);
    res.rmax=max(r.rmax,r.sum+l.rmax);
    res.seg=max(max(l.seg,r.seg),l.rmax+r.lmax);
    return res;
}
void build(int k,int l,int r){
    if(l==r) return nt.lmax=nt.rmax=nt.sum=nt.seg=in[l],void();
    int mid=(l+r)  1;
    build(ls(k),l,mid);
    build(rs(k),mid+1,r);
    nt=merge(lt,rt);
}
Node query(int k,int l,int r,int x,int y){
    if(l =x  r =y) return nt;
    int mid=(l+r)  1,flag=false;
    Node res;
    if(x =mid) res=query(ls(k),l,mid,x,y),flag=true;
    if(y mid){
        Node rson=query(rs(k),mid+1,r,x,y);
        if(!flag) res=rson;
        else res=merge(res,rson);
    }
    return res;
}
inline void subtask(){
    cin  n;for(int i=1;i =n;i++) cin  in[i];cin  m;
    build(1,1,n);
    while(m--){
        int l,r;cin  l  r;
        cout  query(1,1,n,l,r).seg  endl;
    }
}
signed main(){
    ios::sync_with_stdio(false);
    int t=1;//cin  t;
    while(t--) subtask();
    return 0;
}
```

## D - M =ab

数学、枚举

https://atcoder.jp/contests/abc296/tasks/abc296_d

**题目描述**

找到两个正整数 $a$ 和 $b$ 满足 $a,b\le n$ 且 $a\times b\ge m$

**笔记**

上来先对 $m$ 开根，然后以为 $a$ 和 $b$ 必然全都大于等于 $\sqrt{m}$，wa了两发，发现忘记了可能一个数很小但另一个数很大

然后发现这是经典讨论题，往往需要枚举一个，且枚举花费的时间复杂度是可以接受的。于是这题只需要枚举 $a$，然后求出最小的 $b$，再看看满不满足条件即可

```cpp
#include bits/stdc++.h 
#define int long long
#define ull unsigned long long
#define ls(k) (k)  1
#define rs(k) (k)  1|1
#define debug(x) cout  #x  "="  x  endl
using namespace std;
const int inf=0x3f3f3f3f3f3f3f3f;
const int mod=0;
typedef pair int,int  pii;
inline int exsqrt(int x){
    int r=sqrt(x);
    while((r+1)*(r+1) =x) r++;
    while((r-1)*(r-1) =x) r--;
    return r;
}
inline void subtask(){
    int n,m;cin  n  m;
    if(n =1000000  n*n m) return cout  -1,void();
    int r=exsqrt(m);
    if(r*r==m) return cout  m,void();
    int ans=inf;
    for(int i=1;i =r+1;i++){
        if(m%i==0){
            if(m/i =n) return cout  m,void();
        }else if((m/i+1) =n) ans=min(ans,i*(m/i+1));
    }
    cout  ans;
}
signed main(){
    ios::sync_with_stdio(false);
    int t=1;//cin  t;
    while(t--) subtask();
    return 0;
}
```

## Nearest vectors

https://codeforces.com/problemset/problem/598/C

**题目描述**

给你 $n(1\le n \le 10^5)$ 个点，然后让你求出所有原点到这个点的向量中夹角最小的那个

**笔记**

先进行极角排序，然后逐个求夹角就可以了

但关键是怎么搞出最小夹角出来

朴素使用点乘求夹角，然后再比较，会有精度损失，只能过 32 个点

开 long double，精度好一点，但只能过 103 个点

我们再卡一卡，把所有坐标乘 1000，有效果，但也只能过 104 个点

搜题解，得知了一种无精度损失的比较夹角的方法：

对于一个角，我们将其旋转，使一条边与 X 轴平行。假设角度为 $\theta$，另一条边向量模长为 $v$，则旋转后的点为 $(v\cos \theta, v \sin \theta)$

我们发现，这两个坐标再同时乘上已经与 X 轴平行的边的模长后，横坐标就变成了点乘，纵坐标就变成了叉乘。而同时乘上一个数是不会改变其与 X ，即原来的边的夹角

对于另外一个角也进行上述操作，于是就转变为判断两个向量，哪个向量与 X 轴夹角更小一点，可以使用叉乘判断

```cpp
//判断OA1和OB1之间的夹角是不是比OA2和OB2之间的夹角更小
inline bool angle_less(Point a1,Point b1,Point a2,Point b2){
    Point t1(a1*b1,abs(a1^b1)),t2(a2*b2,abs(a2^b2));
    return (t1^t2) 0;
}
```

## P3349 [ZJOI2016] 小星星

https://www.luogu.com.cn/problem/P3349

**题目描述**

给出一个包含 $n$ 个点的树，以及 $n$ 个点 $m$ 条边的图。现在你需要给这个树每个点分配一个序号，分配的应该为 $n$ 的排列。分配后需要满足如果两个点在树上有连边，那么也应该在图上有连边。求分配方案数

**数据范围**

$1\le m\le 17$

**笔记**

考虑 dp，dp 的时候，为了保证分配序号时不会分配重复，我们就遇到了后效性的问题。解决后效性可以把有后效性的因素放到状态里，于是我们可以设 $dp[x][i][S]$ 表示给 $x$ 点分配序号 $i$ ，其子节点分配序号集合为 $S$ 时的方案数。但这样大力 dp 的时间复杂度太高

考虑放松限制。如果我们不必让分配的序号满足是一个排列，那么 dp 就可以变为 $dp[x][i]$。但这样算出来的方案中，可能存在两点分配的序号是相同的。此时就可以考虑容斥了，我们枚举 $\{1,...,n\}$ 的子集 $S$。令 $dp[x][i]$ 表示配分在集合 $S$ 中的序号时的方案数。我们计算出 $|S|=n$ 时方案数，减去 $|S|=n-1$ 时方案数，加上 $|S|=n-2$ 时方案数，即可得到答案

```cpp
#include bits/stdc++.h 
#define int long long
#define ull unsigned long long
#define ls(k) (k)  1
#define rs(k) (k)  1|1
#define debug(x) cout  #x  "="  x  endl
using namespace std;
const int inf=0x3f3f3f3f3f3f3f3f;
const int mod=0;
typedef pair int,int  pii;
int now,dp[18][18],n,m;
vector int  ve[18],ma[18];
void dfs(int x,int fa){
    for(int i=1;i =n;i++) if((now (1  (i-1)))) dp[x][i]=1;
    for(auto to:ve[x]){
        if(to==fa) continue;
        dfs(to,x);
        for(int i=1;i =n;i++){
            if(!(now (1  (i-1)))) continue;
            int s=0;
            for(auto j:ma[i]){
                if(!(now (1  (j-1)))) continue;
                s+=dp[to][j];
            }
            dp[x][i]*=s;
        }
    }
}
inline int popcnt(int x){
    int res=0;
    while(x){
        if(x 1) res++;
        x  =1;
    }
    return res;
}
inline void subtask(){
    cin  n  m;
    for(int i=1;i =m;i++){
        int u,v;cin  u  v;
        ma[u].push_back(v);
        ma[v].push_back(u);
    }
    for(int i=1;i n;i++){
        int u,v;cin  u  v;
        ve[u].push_back(v);
        ve[v].push_back(u);
    }
    int ans=0;
    for(now=1;now (1  n);now++){
        memset(dp,0,sizeof(dp));
        dfs(1,1);
        int tmp=0;
        for(int i=1;i =n;i++){
            if(!(now (1  (i-1)))) continue;
            tmp+=dp[1][i];
        }
        //debug(now);debug(tmp);
        if((n-popcnt(now))%2) ans-=tmp;
        else ans+=tmp;
    }
    cout  ans;
}
signed main(){
    ios::sync_with_stdio(false);
    int t=1;//cin  t;
    while(t--) subtask();
    return 0;
}
```

## P6628 [省选联考 2020 B 卷] 丁香之路

https://www.luogu.com.cn/problem/P6628

贪心+欧拉路+最小生成树

**题目描述**

求 $s$ 到 $i(1\le i \le n)$  的最短路，要求必须经过指定的 $m$ 条边，至少经过一次。点 $x$ 到点 $y$ 的距离为 $|x-y|$ 

**数据范围**

$1\le n \le 2500$

保证 $1\le s\le n$；保证 $m\le \frac {n(n-1)}2$

**笔记**

如果若有的边都恰好走一次，那么就很像欧拉路问题了。现在所有的边可以不止经过一次，那么我们可以考虑加入一些重复边，转化为欧拉路问题。

我们知道，只要度数均为偶数，那么一定存在欧拉路，于是我们现在只需要想办法加入一些边，让所有的点的度数变成偶数

由于欧拉路还需要两个度数是奇数的点，不太好处理。我们考虑给起点和终点连接一条边权，此时就转为了欧拉回路了

因为题目还要求是最短路，因此我们加入的边权之和应最小

首先考虑将边的度数变成偶数，我们把点的编号从小到大排序，然后直接给相邻的两个度数为奇数的点连边就可以了。仔细思考原图的性质，能够发现度数为奇数的点一定有偶数个，可以两两配对

然后现在我们还面临着连通性的问题。在上面将边的度数变成偶数的连边过程中，对于点 $u$ 和 $v$，$u v$，我们不去直接将他俩连边，而是选择连接 $(u,u+1)$、$(u+1,u+2)$、......、$(v-1,v)$。这样的话，产生的边权还是一样的，中间的点因为多连了两条边，度数的奇偶性没有发生变化，但是我们多把一些点连接了起来，感性上可以发现能够让连通性变得更强一点。

但还是可能有连通块之间没有连通。我们考虑把涉及到的这些点编号从小到大排序，然后两两连边，跑最小生成树，以最小的代价将整个图连通。值得注意的是跑最小生成树时建边时应该建两个重复的边，来保持度数是偶数。

```cpp
#include bits/stdc++.h 
#define int long long
#define ull unsigned long long
#define ls(k) (k)  1
#define rs(k) (k)  1|1
#define debug(x) cout  #x  "="  x  endl
using namespace std;
const int inf=0x3f3f3f3f3f3f3f3f;
const int mod=0;
typedef pair int,int  pii;
#define _ 2502
inline int dis(int u,int v){return abs(u-v);}
struct UFS{
    int fa[_],n;
    UFS(int n){for(int i=1;i =n;i++) fa[i]=i;this- n=n;}
    UFS(const UFS  old){
        n=old.n;
        for(int i=1;i =old.n;i++) fa[i]=old.fa[i];
    }
    int find(int x){while(x!=fa[x]) x=fa[x]=fa[fa[x]];return x;}
    void merge(int x,int y){fa[find(x)]=find(y);}
};
set int  se;
int de1[_],de2[_],n,m,s;
struct Edge{int u,v,w;} edge[_];
int solve(UFS u2,int x){
    for(int i=1;i =n;i++) de2[i]=de1[i];
    de2[s]++,de2[x]++;
    int res=0,las=0,pre=0,cnt=0;
    for(auto it=se.begin();it!=se.end();it++){
        int now=*it;
        if(it!=se.begin()) edge[++cnt]={las,now,dis(las,now)};
        las=now;
        if(de2[now]%2==0) continue;
        else if(!pre) pre=now;
        else{
            res+=dis(pre,now);
            for(int i=pre+1;i =now;i++) u2.merge(i-1,i);
            pre=0;
        }
    }
    sort(edge+1,edge+cnt+1,[](Edge x,Edge y){return x.w y.w;});
    for(int i=1;i =cnt;i++){
        int u=edge[i].u,v=edge[i].v;
        if(u2.find(u)==u2.find(v)) continue;
        res+=2*edge[i].w;
        u2.merge(u,v);
    }
    return res;
}
inline void subtask(){
    cin  n  m  s;se.insert(s);
    UFS u1(n);
    int base=0;
    for(int i=1;i =m;i++){
        int u,v;cin  u  v;
        se.insert(u),se.insert(v);
        de1[u]++,de1[v]++;
        base+=dis(u,v);
        u1.merge(u,v);
    }
    for(int i=1;i =n;i++){
        se.insert(i);
        cout  base+solve(u1,i)  " ";
        if(!de1[i]  i!=s) se.erase(i);
    }
}
signed main(){
    ios::sync_with_stdio(false);
    int t=1;//cin  t;
    while(t--) subtask();
    return 0;
}
```




