首页 > 其他分享 >POJ3608(旋转卡壳--求两凸包的最近点对距离)

POJ3608(旋转卡壳--求两凸包的最近点对距离)

时间:2023-05-31 23:35:09浏览次数:56  
标签:include Point -- double int ymaxQ 顶点 两凸包 POJ3608


题目:Bridge Across Islands

 

 

考虑如下的算法, 算法的输入是两个分别有m和n个顺时针给定顶点的凸多边形P和Q。

1.计算P上y坐标值最小的顶点(称为 yminP )和Q上y坐标值最大的顶点(称为 ymaxQ)。

2.为多边形在 yminP 和 ymaxQ 处构造两条切线 LP 和 LQ 使得他们对应的多边形位于他们的右侧。

  此时 LP 和 LQ 拥有不同的方向, 并且 yminP 和 ymaxQ 成为了多边形间的一个对踵点对。

3.计算距离(yminP,ymaxQ) 并且将其维护为当前最小值。

4.顺时针同时旋转平行线直到其中一个与其所在的多边形的边重合。

5.如果只有一条线与边重合, 那么只需要计算“顶点-边”对踵点对和“顶点-顶点”对踵点对距离。 都将他们与当前最小值

比较, 如果小于当前最小值则进行替换更新。如果两条切线都与边重合,那么情况就更加复杂了。如果边“交叠”,也就是

可以构造一条与两条边都相交的公垂线(但不是在顶点处相交), 那么就计算“边-边”距离。 否则计算三个新的“顶点-顶

点”对踵点对距离。 所有的这些距离都与当前最小值进行比较, 若小于当前最小值则更新替换。

6.重复执行步骤4和步骤5, 直到新的点对为(yminP,ymaxQ)。

7.输出最小距离。


#include <iostream>
#include <string.h>
#include <algorithm>
#include <stdio.h>
#include <math.h>

using namespace std;

const int N=50000;
const double eps=1e-9;
const double INF=1e99;

struct Point
{
    double x,y;
};

Point P[N],Q[N];

double cross(Point A,Point B,Point C)
{
    return (B.x-A.x)*(C.y-A.y)-(B.y-A.y)*(C.x-A.x);
}

double dist(Point A,Point B)
{
    return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));
}

double multi(Point A,Point B,Point C)
{
    return (B.x-A.x)*(C.x-A.x)+(B.y-A.y)*(C.y-A.y);
}

//顺时针排序
void anticlockwise(Point p[],int n)
{
    for(int i=0;i<n-2;i++)
    {
        double tmp=cross(p[i],p[i+1],p[i+2]);
        if(tmp>eps) return;
        else if(tmp<-eps)
        {
            reverse(p,p+n);
            return;
        }
    }
}

//计算C点到直线AB的最短距离
double Getdist(Point A,Point B,Point C)
{
    if(dist(A,B)<eps) return dist(B,C);
    if(multi(A,B,C)<-eps) return dist(A,C);
    if(multi(B,A,C)<-eps) return dist(B,C);
    return fabs(cross(A,B,C)/dist(A,B));
}

//求一条直线的两端点到另外一条直线的距离,反过来一样,共4种情况
double MinDist(Point A,Point B,Point C,Point D)
{
    return min(min(Getdist(A,B,C),Getdist(A,B,D)),min(Getdist(C,D,A),Getdist(C,D,B)));
}

double Solve(Point P[],Point Q[],int n,int m)
{
    int yminP=0,ymaxQ=0;
    for(int i=0;i<n;i++)
       if(P[i].y<P[yminP].y)
          yminP=i;
    for(int i=0;i<m;i++)
       if(Q[i].y>Q[ymaxQ].y)
          ymaxQ=i;
    P[n]=P[0];
    Q[m]=Q[0];
    double tmp,ans=INF;
    for(int i=0;i<n;i++)
    {
        while(tmp=cross(P[yminP+1],Q[ymaxQ+1],P[yminP])-cross(P[yminP+1],Q[ymaxQ],P[yminP])>eps)
            ymaxQ=(ymaxQ+1)%m;
        if(tmp<-eps) ans=min(ans,Getdist(P[yminP],P[yminP+1],Q[ymaxQ]));
        else         ans=min(ans,MinDist(P[yminP],P[yminP+1],Q[ymaxQ],Q[ymaxQ+1]));
        yminP=(yminP+1)%n;
    }
    return ans;
}

int main()
{
    int n,m;
    while(cin>>n>>m)
    {
        if(n==0&&m==0) break;
        for(int i=0;i<n;i++)
           cin>>P[i].x>>P[i].y;
        for(int i=0;i<m;i++)
           cin>>Q[i].x>>Q[i].y;
        anticlockwise(P,n);
        anticlockwise(Q,m);
        printf("%.5lf\n",min(Solve(P,Q,n,m),Solve(Q,P,m,n)));
    }
    return 0;
}


标签:include,Point,--,double,int,ymaxQ,顶点,两凸包,POJ3608
From: https://blog.51cto.com/u_16146153/6391057

相关文章

  • HDU4372(第一类斯特林数)
    题目:CounttheBuildings题意:N座高楼,高度均不同且为1~N中的数,从前向后看能看到F个,从后向前看能看到B个,问有多少种可能的排列数。0<N,F,B<=2000首先我们知道一个结论:n的环排列的个数与n-1个元素的排列的个数相等,因为P(n,n)/n=(n-1)!。可以肯定,无论从最左边还是从最右边看,......
  • java List分批处理
    1packagecom.example.demo;2importcom.google.common.collect.Lists;3importjava.util.ArrayList;4importjava.util.List;5publicclassTest{6publicstaticvoidmain(String[]args){7List<Integer>list=newArrayList<......
  • 容斥原理应用(求1~r中有多少个数与n互素)
    问题:求1~r中有多少个数与n互素。对于这个问题由容斥原理,我们有3种写法,其实效率差不多。分别是:dfs,队列数组,位运算。先说说位运算吧:用二进制1,0来表示第几个素因子是否被用到,如m=3,三个因子是2,3,5,则i=3时二进制是011,表示第2、3个因子被用到LLSolve(LLn,LLr){vector<LL>p;......
  • HDU4633(Polya计数)
    题目:Who'sAuntZhang#include<iostream>#include<string.h>#include<stdio.h>usingnamespacestd;typedeflonglongLL;constLLMOD=10007;LLquick_mod(LLa,LLb){LLans=1;a%=MOD;while(b){if(b&1......
  • centos 安装iftop命令
    要在CentOS中安装iftop命令,可以使用以下命令: yuminstallepel-release-yyuminstalliftop-y其他debian系統命令一、尽快连接服务器,查看异常流量,这里我推荐使用iftop;安装并启动iftop:aptupdateaptinstalliftopiftop二、iftop查看异常流量的IP,然后使用防火墙禁止;当......
  • HDU4382(特殊的矩阵连乘)
    题目:HarryPotterandCyberSequenceGenerator题意,有两个容器C1,C2,初始的时候C1中有一个数的值为V,给你K个操作,每次都重复这K个操作N遍,最后问你C2中的数是   多少。N<=10^100。1:循环操作的次数巨大,敏感的想到这是矩阵连乘的题目。2:K个操作可以得出一个矩阵,N个K操作就是这个......
  • Python基于粒子群优化的投资组合优化研究|附代码数据
    全文链接:http://tecdat.cn/?p=6811最近我们被客户要求撰写关于粒子群优化的研究报告,包括一些图形和统计输出。粒子群优化(PSO)在PSO中,群中的每个粒子表示为向量。在投资组合优化的背景下,这是一个权重向量,表示每个资产的分配资本。矢量转换为多维搜索空间中的位置。每个粒子也会记......
  • 连分数
    对于连分数,我们可以表示为:对于无理数,ai一定是无穷数列,反之,对于有理数,ai一定是有穷数列。对于上式中的p与q,有递推式:而对于sqrt(n)来说,ai中的首项为一个单独的整数,除了它后面的都会循环。下面我们来分析一个关于连分数的题目。题目:连分数题意:给两个整数n和k,n<=10^6,k<=10^9,sqrt(n)可以......
  • Vue2实现双向数据绑定原理
    Vue2.x采用数据劫持结合发布订阅模式(PubSub模式)的方式,通过Object.defineProperty来劫持各个属性的setter、getter,在数据变动时发布消息给订阅者,触发相应的监听回调。当把一个普通Javascript对象传给Vue实例来作为它的data选项时,Vue将遍历它的属性,用Object.defineProp......
  • NEFU704(AC自动机+状态压缩)
    题目:PasswordLeakage#include<iostream>#include<string.h>#include<stdio.h>#include<queue>usingnamespacestd;charS[1000010];charkeyword[51];charstr[51];charT[51];classTrie{public:intcount;Trie*fa......