模板 2018-01-26 计算几何 多边形相关 多边形面积 凸包 旋转卡壳

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
double triangle_area(dot a,dot b,dot c){//三角形面积
    //已知三点坐标,求面积
    return fabs(0.5*((a.x-b.x)*(c.y-b.y)-(c.x-b.x)*(a.y-b.y)));
}

double triangle_area(double a,double b,double c,bool three_sides){//三角形面积
    if(three_sides==true){
        //已知三边边长,求面积
        double p;
        p=0.5*a+0.5*b+0.5*c;
        return sqrt(p*(p-a)*(p-b)*(p-c));//海伦公式
    }
    //已知两边边长a和b,与其夹角弧度值c
    return 0.5*a*b*sin(c);
}

double polygon_area(dot* data,int n)
{//多边形面积,考虑到了凸多边形和凹多边形
    //这些点已经按顺时针或者逆时针排好了
    //n表示有n个点
    double res=0;
    for(int i=1;i<n-1;i++)
        res+=(data[i].x-data[0].x)*(data[i+1].y-data[0].y)-(data[i].y-data[0].y)*(data[i+1].x-data[0].x);
    return fabs(res);//有可能是负的,但是不影响大小
}

bool is_convex(dot poly[],int n){//判断这个是不是凸多边形
    //顺时针逆时针均可
    bool s[3];
    memset(s,0,sizeof(s));
    for(int i=0;i<n;i++)
    {
        s[sign((poly[(i+1)%n]-poly[i])^(poly[(i+2)%n]-poly[i]))+1]=true;
        if(s[0]&&s[2]) return false;
    }
    return true;
}

int dot_in_convexpoly(dot a,dot p[],int n){//判断点a在凸多边形内
    //多边形的点形成一个凸包且排列为逆时针
    for(int i=0;i<n;i++)//点从0到n-1计数
    {//顺时针的话就把if条件里面的<0改为>0
        if(sign((p[i]-a)^(p[(i+1)%n]))<0) return -1;//点在多边形外
        else if(dot_on_segment(a,line(p[i],p[(i+1)%n]))) return 0;//点在多边形上
    }
    return 1;//点在多边形内
}

int dot_in_poly(dot a,dot p[],int n){//判断点是否在任意的多边形内（凹多边形亦可）
    int cnt=0;
    line ray(a,dot(-100000000000.0,a.y)),side;
    for(int i=0;i<n;i++)
    {
        side=line(p[i],p[(i+1)%n]);
        if(dot_on_segment(a,side)) return 0;//点在多边形上
        if(sign(side.s.y-side.e.y)==0) continue;
        if(dot_on_segment(side.s,ray)){
            if(sign(side.s.y-side.e.y)>0) cnt++;
        }
        else if(dot_on_segment(side.e,ray)){
            if(sign(side.e.y-side.s.y)>0) cnt++;
        }
        else if(segment_inter(ray,side)) cnt++;
    }
    if(cnt%2==1) return 1;//点在多边形内
    return -1;//点在多边形外
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
dot O;//原点
bool cmp(dot p1,dot p2)
{//极角排序函数，角度相同则距离原点近的的在前面
    double tmp=(p1-O)^(p2-O);
    if (tmp>0) return 1;
    if (tmp==0 && dot(O-p1).length()<dot(O-p2).length()) return 1;
    return 0;
}

int work_on_convex_hull(dot data[],int n,int result[])
{
    //直接将凸包图形的序号写进result[]，并返回有多少个凸包顶点,排列为顺时针
    //原始的输入数据data[]
    //result[]里面记录的是编号，这个编号是用于在data[]里面寻找点的.
    //res记录的是寻找出来的凸包究竟有多少个点,并作为函数返回值返回
    int i,origin,res;
    origin=0;
    for(i=1;i<n;i++)
        if((data[origin].x>data[i].x)||((data[origin].x==data[i].x)&&(data[origin].y>data[i].y)))
            origin=i;
    O=data[origin];//可能碰上不能直接复制结构体的情况，更换语句就可以了
    data[origin]=data[0];
    data[0]=O;//交换data中第0点和真正的原点的位置
    sort(data+1,data+n,cmp);
    if(n==1){
        res=1; result[0]=0;//改变这里可以改变result数组存的是编号还是结构体
    }
    else if(n==2){
        res=2; result[0]=0; result[1]=1;//改变这里可以改变result数组存的是编号还是结构体
    }
    else if(n>2){
        res=0;result[0]=0;//鬼畜*3
        for (int i=1;i<n;i++){
            while(res>0 &&((data[result[res-1]]-data[result[res]])^(data[i]-data[result[res]]))>=0) res--;
            res++;result[res]=i;//鬼畜*4
        }
        res++;
    }
    else res=0;
    return res;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
double rotating_calipers(dot data[],int n)
{//旋转卡壳求最远点距
    //前提：已经使用过work_on_convex_hull
    int i=1,j;
    double res=0;
    data[n]=data[0];//这里这样做是怕你跑到外面去
    for(j=0;j<n;j++)
    {
        while(((data[i+1]-data[j+1])^(data[j]-data[j+1]))>((data[i]-data[j+1])^(data[j]-data[j+1])))
            i=(i+1)%n;//取余是怕你跑到外面去
        res=max(res,max(dot(data[j]-data[i]).length(),dot(data[j+1]-data[i+1]).length()));
    }
    return res;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int main()
{
    dot data[1000],graph[1000];
    int i,n,num,res[1000];
    while(scanf("%d",&n)!=EOF)
    {
        for(i=0;i<n;i++)
            scanf("%lf%lf",&data[i].x,&data[i].y);
        num=work_on_convex_hull(n,data,res);
        printf("This graph has %d dotsn",num);
        for(i=0;i<num;i++)
        {
            printf("%dth dot%d  x:%lf y:%lfn",i,res[i],data[res[i]].x,data[res[i]].y);//本模版使用方式可以看这一行
            graph[i]=data[res[i]];
        }
        cout<<rotating_calipers(graph,num)<<endl;
            
    }
    return 0;
}