本文共 14355 字，大约阅读时间需要 47 分钟。

判断点和射线的那边

向量叉乘判断符号解决。向量叉乘使用右手法则。

$$\begin{gathered} v_1=(x1,y1),v2=(x2,y2) \\ v1\times v2=x1\ast y2-y1\ast x2 \end{gathered}$$ 例： 依次给出三个点，求是顺时针旋转还是逆时针。 $$s=v_{13}\times v_{23}=(x1-x3)(y2-y3)-(y1-y3)(x2-x3)$$ 则结合右手法则可知， { s < 0 , 顺 时 针 s > 0 , 逆 时 针 \{\begin{aligned}s<0, 顺时针\\ s>0, 逆时针\end{aligned} {

s<0,顺时针s>0,逆时针​

判断n个线段能否投影到一条直线上至少有一个共同点。容易转化为问题：n个线段是否能被一条直线（与投影轴垂直）穿过。枚举所有点两两成的直线能否串过所有线段。用跨立实验判断直线和线段是否相交。

#include
   
    #include
    
     #include
     
      #include
      
     
    
   

求两直线交点

x0 = ((x3-x4) * (x2*y1 - x1*y2) - (x1-x2) * (x4*y3 - x3*y4)) / ((x3-x4) * (y1-y2) - (x1-x2) * (y3-y4));y0 = ((y3-y4) * (y2*x1 - y1*x2) - (y1-y2) * (y4*x3 - y3*x4)) / ((y3-y4) * (x1-x2) - (y1-y2) * (x3-x4));

#include
   
    #include
    
     #include
     
      #include 
      
       #include
       
      
     
    
   

每个点两两看有没有穿过墙，没穿过则建边，跑最短路。 没有做快速排斥实验，因为不可能有边与墙共线的情况。

#include
   
    #include
    
     #include
     
      #include
      
     
    
   

木棒压木棒，求没被压的木棒。

#include
   
    #include
    
     #include
     
      #include 
      
       #include
       
      
     
    
   

每次从线段的中点穿过，问穿过多少面墙能到达宝藏位置。由于每条直线穿过整个正方形。转弯无法减少穿过数。所以枚举每个中点作射线就行。而枚举每个顶点也一样。

#include
   
    #include
    
     #include
     
      #include 
      
       #include
       
      
     
    
   

从Plant A出发，只能往左转最多能走多少个点，依次输出。只要每次选当前点为基准，极角排序，选极角最小的，必能走完所有的点。

#include
   
    #include
    
     #include
     
      #include 
      
       #include
       
      
     
    
   

给出N个乱序的点，问这些点能不能组成正N边形。 思路：先找到y坐标最小的那个点，作为第一个点，将后面N-1个点依次以上一个点为KEY点做极角排序。判断每条边长度是否相同，相邻边的角度是否相同（可用内积，外积）。

#include 
   
    #define endl '\n'using namespace std;const int inf = 2e9;const double eps = 1e-6;using ll = long long;struct Point{
       int x, y;    double len(){
           return sqrt(1ll*x*x+1ll*y*y);    }    Point operator- (const Point& ot) const{
           return Point{
   x-ot.x, y-ot.y};    }    ll operator* (const Point& ot) const{
           return x*ot.y - y*ot.x;    }}key;int sgn(double x){
       if(x==0)return 0;    return x < 0 ? -1 : 1;}bool cmp(const Point& a, const Point& b){
       Point va = a - key, vb = b - key;    switch(sgn(va * vb)){
       case 0:        return va.len() < vb.len();    case 1:        return 1;    case -1:        return 0;    }}int main(){
       int tt;    ios::sync_with_stdio(false);    cin.tie(0), cout.tie(0);    cin >> tt;    while(tt--){
           int n;        cin >> n;        vector
    
      v;        int idx = 0;        for(int i=0;i
     
      > x.x >> x.y;            v.push_back(x);            if(x.y < v[0].y || x.y==v[0].y && x.x < v[0].x)                swap(v[i], v[0]);        }        for(int i=0;i+1
     
    
   

求二维凸包的周长。

#include 
   
    #define endl '\n'using namespace std;const int inf = 2e9;const double eps = 1e-6;using ll = long long;using pdd = pair
    
     ;const double PI = acos(-1);const int maxn = 2e5+5;int sgn(double x){
       if(x==0)return 0;    return x < 0 ? -1 : 1;}struct Point{
       int x, y;    double len(){
           return sqrt(1ll*x*x+1ll*y*y);    }    Point operator- (const Point& ot) const{
           return Point{
   x-ot.x, y-ot.y};    }    ll operator* (const Point& ot) const{
           return x*ot.y - y*ot.x;    }}key, sta[maxn];bool cmp(const Point& a, const Point& b){
       Point va = a - key, vb = b - key;    switch(sgn(va * vb)){
       case 0:        return va.len() < vb.len();    case 1:        return 1;    case -1:        return 0;    }}int main(){
       int tt;    ios::sync_with_stdio(false);    cin.tie(0), cout.tie(0);    int n;    while(cin >> n && n){
           vector
     
       v(n);        for(Point& p : v){
               cin >> p.x >> p.y;        }        if(n==1){
               cout << 0 << endl;            continue;        }else if(n==2){
               cout << fixed << setprecision(2) << (v[1] - v[0]).len() << endl;            continue;        }        int id = 0;        for(int i=1;i
      
        0 && sgn( (sta[top] - sta[top-1]) * (v[i] - sta[top]) ) < 0)                top--; // 踢掉右转的            sta[++top] = v[i];        }        double sum = 0;        sta[++top] = v[0];        for(int i=0;i
      
     
    
   

旋转卡壳

题意：二维平面给一堆点，求最小的矩形包括所有的点。输出矩形面积和4个坐标。 思路：旋转卡壳模板。维护三个卡壳点，因为三者都是单峰函数，所以可以实现。

• p是离当前枚举边$(i,i+1)$最远的点，用叉乘求三角形面积来判断，通过p就求出了矩形的高H
• fr是所有点投影到当前枚举边$(i,i+1)$，设$i$到$i+1$为正方向，最负的点
• ba是最正的点，fr、ba使用点乘求投影来判断

#include
   
    // #define endl '\n'#define IOS ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);using namespace std;const int N = 5e4 +5;const double eps = 1e-10;struct Coor{
       double x, y;    double operator^ (const Coor & ot) const &{
           return x * ot.y - y * ot.x;    }    double operator* (const Coor & ot) const &{
           return x * ot.x + y * ot.y;    }    double len(){
           return sqrt(x * x + y * y);    }    Coor operator- (const Coor & ot) const &{
           return Coor{
   x - ot.x, y - ot.y};    }    Coor operator+ (const Coor & ot) const &{
           return Coor{
   x + ot.x, y + ot.y};    }}a[N], sta[N], key, rect[4];Coor operator* (const double & c, const Coor & v){
       return Coor{
   v.x * c, v.y * c};}int sgn(double v){
       if(abs(v) < eps)return 0;    return v < 0 ? -1 : 1;}bool cmp(const Coor &a, const Coor &b){
       Coor da = a - key, db = b - key;    switch(sgn(da ^ db)){
       case 1:        return true;    case -1:        return false;    default:        return da.len() < db.len();    }}double area(int i, int j, int k){
       return (sta[j] - sta[i]) ^ (sta[k] - sta[i]);}double project(int i, int j, int k){
       return (sta[j] - sta[i]) * (sta[k] - sta[i]);}int main(){
       IOS;    int n;    cin >> n;    int id = 0;    for(int i = 0; i < n; ++i){
           cin >> a[i].x >> a[i].y;        if(a[i].y < a[id].y || a[i].y == a[id].y && a[i].x < a[id].x)id = i;    }    swap(a[id], a[0]);    key = a[0];    sort(a+1, a+n, cmp);    int top = 0;    sta[0] = a[0];#define U(_ar, _i) cout << "(" << _ar[_i].x << "," << _ar[_i].y << ") ";    for(int i = 1; i < n; ++i){
           while(top > 0 && sgn((sta[top] - sta[top - 1]) ^ (a[i] - sta[top])) <= 0)top--;        sta[++top] = a[i];    }    sta[++top] = sta[0];    int p = 1, ba = 1, fr = 1;    double ans = 2e14;    for(int i = 0; i < top; ++i){
           while(sgn(area(i, i + 1, p) - area(i, i + 1, p + 1)) <= 0)            p = (p + 1) % top;        while(sgn(project(i, i + 1, fr)) > 0 || sgn(project(i, i + 1, fr) - project(i, i + 1, (fr + 1) % top)) >= 0)            fr = (fr + 1) % top;        while(sgn(project(i, i + 1, ba) - project(i, i + 1, (ba + 1) % top)) < 0)            ba = (ba + 1) % top;        double L = (sta[i + 1] - sta[i]).len(), H = area(i, i + 1, p), C = (sta[i + 1] - sta[i]) * (sta[ba] - sta[fr]);//        assert(sgn(C) > 0);//        assert(sgn(H) > 0);        if(sgn(H * C - ans * L * L) < 0){
               ans = H * C / (L * L);            H /= L;            Coor I = 1 / L * (sta[i + 1] - sta[i]); // 单位向量            double pf = (sta[fr] - sta[i]) * I; // f投影大小            double pb = (sta[ba] - sta[i]) * I; // b投影大小            rect[0] = sta[i] + pf * I;            rect[1] = sta[i] + pb * I;            Coor Vert = sgn(I.y) == 0 ? Coor{
   0, 1} : Coor{
   1, -I.x / I.y};            if(sgn(I ^ Vert) < 0)Vert = -1 * Vert;            Vert = H / Vert.len() * Vert;            rect[2] = rect[1] + Vert;            rect[3] = rect[0] + Vert;//            cout << ans << endl;//            for(int fi = 0, i = 0; i < 4; ++i){
   //                cout << rect[fi].x << " " << rect[fi].y << endl;//                fi = (fi + 1) % 4;//            }        }    }    if(sgn(ans) == 0) ans = 0;    cout << fixed << setprecision(5) << ans + 1e-8 << endl;    int fi = 0;    for(int i = 1; i < 4; ++i){
           if(sgn(rect[i].y - rect[fi].y) < 0 || sgn(rect[i].y - rect[fi].y) == 0 && sgn(rect[i].x - rect[fi].x) < 0)            fi = i;    }    for(int i = 0; i < 4; ++i){
           if(sgn(rect[fi].x) == 0)rect[fi].x = 0;        if(sgn(rect[fi].y) == 0)rect[fi].y = 0;        cout << rect[fi].x << " " << rect[fi].y << endl;        fi = (fi + 1) % 4;    }}
   

转载地址：http://lgkzi.baihongyu.com/