欢迎您光临bv1946伟德体育官方网站!

寄蒜几盒极速入门

时间:2019-12-09 02:30

图片 1图片 2

三种算法都有叁个贴近上边包车型地铁说话:


假设要判断的边i,那么判断边i和边i-1,边i和边i+1的夹角是否都为0(180)。                                        ----XDruid
struct ln{
    po p,v;
}l[N];
bool comp(ln x,ln y){
    db t=x.v*y.v;
    return (t>0)||((t==0)&&x.v*(y.p-x.p)>0);
}//先右后左 如果平行则返通过起点连线与向量方向判定
bool lcmp(ln x,ln y){
    if (x.v.y==0&&y.v.y==0) return x.v.x<y.v.x;
    if (x.v.y<=0&&y.v.y<=0) return comp(x,y);
    if (x.v.y>0&&y.v.y>0) return comp(x,y);
    return x.v.y<y.v.y;//逆时针
}
bool left(ln x,po p) { return x.v*(p-x.p)>0; }//点在线左边则点与起点向量在原向量左
po jd(ln x,ln y){
    po t=x.p-y.p;
    db u=(y.v*t)/(y.v,x.v);
    return x.p+u*x.v;
}//利用面积之比 同底高之比
void hpi(){
    sort(l+1,l+n+1,lcmp);
    int m=0;
    for (int i=1;i<=n;++i){
        if (l[i].v*l[i-1].v||i==1) m++;//平行特判
        l[m]=l[i];
    }
    int h=1,t=2; s[1]=l[1],s[2]=l[2];
    for (int i=3;i<=m;++i){
        while (h<t&&left(l[i],jd(s[t],s[t-1]))) t--;
        while (h<t&&left(l[i],jd(s[h],s[h+1]))) h++;
        s[++t]=l[i];
    }
    while (h<t&&left(s[h],jd(s[t],s[t-1]))) t--;
    while (h<t&&left(s[t],jd(s[h],s[h+1]))) h++;//消除无用
    s[++t]=s[h];//形成环
    for (int i=h;i<t;++i) p[++cnt]=jd(s[i],s[i+1]);
}

1.基于水平序的Andrew算法

那样的话,求出来正是最简凸包,即点数尽量少的凸包,因为Cross== 0的动静也被出栈了,所以一条凸包边上就能够三点共线了。

那题就在于求凸包的内部原因了,求凸包有三种算法: 

db polys(po *p,int n){
    db res=0;
    for (int i=1;i<n-1;++i) res+=(p[i]-p[0])*(p[i+1]-p[0]);
    return res/2;
}

解法: 稳定凸包每条边上至稀少四个点。

typedef double db;
struct po{
    db x,y;
    po (db x=0,y=0):x(x),y(y) {}
};
const db eps=1e-9;
po operator + (po a,po b) { return po(a.x+b.x,a.y+b.y); }
po operator - (po a,po b) { return po(a.x-b.x,a.y-b.y); }
po operator * (po a,db b) { return po(a.x*b,a.y*b); }
po operator / (po a,db b) { return po(a.x/b,a.y/b); }
db sqr(db x) { return x*x; }
db dis(po a,po b) { return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y)); }
int cmp(db x) { return fabs(x)<eps?0:(x<0?-1:1); }
bool operator == (po a,po b) { return (!cmp(a.x-b.x))&&(!cmp(a.y-b.y));  }

用作那么些题,大家怎么求其实都能够:

int xx(po a){
    if (a.x>0&&a.y>=0) return 1;
    if (a.x<=0&&a.y>0) return 2;
    if (a.x<0&&a.y<=0) return 3;
    return 4;
}
bool jcmp(po a,po b){
    if (a==b) return 1;
    po x=a-o,y=b-o; int l=xx(x),r=xx(y);
    if (l==r) return (x*y<0)||(x*y==0&&x.x<y.x);
    return l<r;
}

图片 3

此处注意我们从0最早然后使其<n的话就能够用取模的艺术循环
以致while这里是还未有等于的
接下来那东西日常还是能拿来求多个凸多边形之间的一丁点儿间隔
枚举在那之中四个的边 然后另三个就搞点就好 那些也是干Baba的

大家把语句改下,把Cross.. <=0  改成 Cross.. < 0 ,那么求的就是最繁凸包,即恐怕一条凸包边上富含超级多点也归于凸包的点。

点/叉积的一些接受

近期算是对团结的凸包版有了完备的刺探了,老妈再也不用忧虑自个儿用错凸包了。哈哈。

  1. 凸包
    先排序 直接按x,y分别为尤为重要字
    先丢八个点步入 然后从第多个点开端
    while不是在前边方向的侧面就弹 契合就加进去
    做五回 分别求出下/上凸包

即上边包车型地铁气象:

这有可能是自己计算机上唯豆蔻梢头三个足以记普通话还足以打代码还足以保留之处了 so sad

2.基于极角序的Graham算法

db operator ^ (po a,po b) { return a.x*b.x+a.y*b.y; }
db operator * (po a,po b) { return a.x*b.y-a.y*b.x; }

View Code

bool tbcmp (po a,po b) { return a.x==b.x?a.y<b.y:a.x<b.x; }
int tb(po *p,int n){
    sort(p+1,p+n+1,chcmp);
    int m=0;
    for (int i=1;i<=n;++i){
        while (m>1&&(st[m]-st[m-1])*(a[i]-st[m-1])<0) m--;
        st[++m]=a[i];
    }
    int k=m;
    for (int i=n-1;i;--i){
        while (m>k&&(st[m]-st[m-1])*(a[i]-st[m-1])<=0) m--;
        st[++m]=a[i];
    }
    return m;
}

 

  1. 向量构造体与主导运算

代码: (这里小编用的是Andrew算法)

  1. 折线拐向
    先是把两点转为二个向量 决断向量之间的周旋地方
    v1=p2-p0 v2=p1-p0
    谈论v1×v2 <0向右拐 >0向左拐 ==0共线 请用移动的眼光来剖断左右!!!

  2. 点在线段上
    风姿罗曼蒂克经是直线很好办 叉积一下判0就能够
    如借使线条将要制止在拉开/反向延长线上 那么判断一下min/max就好

  3. 判线段p0p1与直线q0q1是不是相交
    鉴于快要没时间了就不看两线段的主题素材了
    令v1=p0-q0,v2=p1-q0,v2=q1-q0 使v1v2与v2v3同号就可以使p0 p1分居直线两边

  4. 点到线段距离
    切记叉积是平行四边形面积 那么就出然后除底边就好
    首先要判垂足是还是不是在线段上 不在则显现为cos为负
    还要cos能够突显出离哪边相当近

  5. 求交点
    能够暴力表达式也许用点和动向表示向量

  6. 极角排序
    大器晚成判象限 二判叉积(依照顺逆定正负卡塔尔 三判x轴间隔

题意: 决断凸包是不是平安。

  1. 动态凸包 大致就用平衡树/cdq来保险凸包 每便投入二个点就找四驱后继来判定这么些点是归属在凸包内/直接参加/要删掉别的点的哪一种境况就好
    不会去学了

2.若是求的是最繁的凸包,就不能用上面的判法,因为怎么判都唯有七个点了,当时可以应用下边包车型大巴秘技:

大概就是以上

1.如若求最简凸包,我们只需推断总共有稍微个点在该凸包边上就能够(端点也算),假如< 3 ,则不符。

6.旋转卡壳 4 3 ka qiao gif此生难忘系列
求平面最远点对
每种点只或者和对踵点有进献 然后这东西是O(n卡塔尔(قطر‎的
咱俩构思枚举一条边 然后找到其间隔最远的点
会造成三角形 然前面积是单峰的
出于是在凸包上做 所早前边的边的对点一定也是干瘪在前边的边的后边的
接下来由于是判面积 那么丢给叉积搞搞就好 然则这里有部分本事(感觉温馨背不下来 依旧手推呢卡塔尔(قطر‎
把面积相比较写成叉积与0比较然后根据叉积是面积有
Cross(A,B) - Cross(A,C) = Cross(A,B-C)
那么就搞后生可畏搞就好了

最简凸包即为紫罗兰色的多个点。 最繁凸包求出的是独具蓝点和红点。

小心几点细节 第二遍弹栈要保险最稀少多个要素 第二回要确认保证大于下凸包成分
然后四次都以<0 次之次还要把等于也弹掉
首次求上凸包从n-1早先 最早导容许要去重

for(int i=0;i<n;i++) {
        while(m > 1 && Cross(ch[m-1]-ch[m-2], p[i]-ch[m-2]) <= 0) m--;
        ch[m++] = p[i];
    }

 

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#define eps 1e-8
using namespace std;

struct Point{
    double x,y;
    Point(double x=0, double y=0):x(x),y(y) {}
    void input() { scanf("%lf%lf",&x,&y); }
};
typedef Point Vector;
int dcmp(double x) {
    if(x < -eps) return -1;
    if(x > eps) return 1;
    return 0;
}
template <class T> T sqr(T x) { return x * x;}
Vector operator + (Vector A, Vector B) { return Vector(A.x + B.x, A.y + B.y); }
Vector operator - (Vector A, Vector B) { return Vector(A.x - B.x, A.y - B.y); }
Vector operator * (Vector A, double p) { return Vector(A.x*p, A.y*p); }
Vector operator / (Vector A, double p) { return Vector(A.x/p, A.y/p); }
bool operator < (const Point& a, const Point& b) { return a.x < b.x || (a.x == b.x && a.y < b.y); }
bool operator >= (const Point& a, const Point& b) { return a.x >= b.x && a.y >= b.y; }
bool operator <= (const Point& a, const Point& b) { return a.x <= b.x && a.y <= b.y; }
bool operator == (const Point& a, const Point& b) { return dcmp(a.x-b.x) == 0 && dcmp(a.y-b.y) == 0; }
double Dot(Vector A, Vector B) { return A.x*B.x + A.y*B.y; }
double Length(Vector A) { return sqrt(Dot(A, A)); }
double Angle(Vector A, Vector B) { return acos(Dot(A, B) / Length(A) / Length(B)); }
double Cross(Vector A, Vector B) { return A.x*B.y - A.y*B.x; }
double angle(Vector v) { return atan2(v.y, v.x); }

bool OnSegment(Point P, Point A, Point B) {         //端点不算
    return dcmp(Cross(A-P,B-P)) == 0 && dcmp(Dot(A-P,B-P)) <= 0;
}
int ConvexHull(Point* p, int n, Point* ch) {
    sort(p,p+n);
    int m = 0;
    for(int i=0;i<n;i++) {
        while(m > 1 && Cross(ch[m-1]-ch[m-2], p[i]-ch[m-2]) <= 0) m--;
        ch[m++] = p[i];
    }
    int k = m;
    for(int i=n-2;i>=0;i--) {
        while(m > k && Cross(ch[m-1]-ch[m-2], p[i]-ch[m-2]) <= 0) m--;
        ch[m++] = p[i];
    }
    if(n > 1) m--;
    return m;
}
Point ch[1006],p[1006];

int main()
{
    int t,n,i,j;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        for(i=0;i<n;i++) p[i].input();
        if(n <= 5) { puts("NO"); continue; }
        int m = ConvexHull(p,n,ch);
        if(m <= 2) { puts("NO"); continue; }
        for(i=0;i<m;i++) {
            int cnt = 0;
            for(j=0;j<n;j++)
                if(OnSegment(p[j],ch[i],ch[(i+1)%m]))
                    cnt++;
            if(cnt < 3) break;
        }
        if(i == m) puts("YES");
        else       puts("NO");
    }
    return 0;
}
db rc(po *p,int n){
    n=tb(p,n),p[0]=p[n];
    db ans=0;
    for (int i=0,j=1;i<n;++i){
        while ((p[i+1]-p[i])*(p[j+1]-p[j])>0) j=(j+1)%n;
        ans=max(ans,max(dis(p[j],p[i]),dis(p[j+1],p[i+1])));
    }
    return ans;
}
  1. 六头形面积
    化成三角形来搞 排个序然后历次叉积最终/2

有的套路
枚举特殊点/边 极角排序后选择单调性 还四天四头能够旋转卡壳
开展叉积 x/y分开管理 二分
另外
地方的板子正确性有待确认

  1. 点积与叉积
    点积是个值 而叉积是个向量
    用的越多的大概是叉积?
    点积 -> x1x2+y1y2 叉积 ->x1y2-x2y1
    点积是二个向量到另叁个向量的投影 乘cos 可以用来求cos
    叉积是笔直与ab向量所成平面包车型地铁向量 是两向量间所成平行四边形的面积 能够用于求sin
    叉积正负能够用来判相对地方
    a×b >0 a在b的顺时针方向 a×b==0共线但不确定同方向
    掌握为a×b正是从a往b扫过去 而从左往右扫为正
  1. 半平面交 又名半个飞机
    先把向量们极角排序 然后写个斜率优化??

操纵跟着cls的课件过二回
要把多少个板子囤好 (据书上说PKU爱考寄蒜几盒板子卡塔尔
不过本人发觉风流倜傥到markdown下本人就喜好折腾
备感制版突然就首要了起来

上一篇:【Python数据分析】四级成绩分布 -matplotlib,xlrd 应用
下一篇:没有了