HDU 6617 Enveloping Convex（凸包+半平面交+二分）

首先对于这m个点维护出一个凸包M，那么问题就变成了判断凸包P进行放大缩小能不能包含凸包M。(凸包P可以进行中心对称变换再进行放大缩小，见题意）

如何判断合适的相似比呢，我们可以用二分去放大缩小凸包P的坐标，得到最小的相似比。

接下来就是如何判断是否包含。我们需要对凸包P上的每一条向量，在凸包M上找到这么一个点，使得这个点左侧的所有凸包M上的点都在向量的左侧，那么我们可以直接同时逆时针枚举，用一个变量维护凸包M上的点，因为是同逆时针，凸包M上的点至少有一个只会被遍历一次，那么复杂度可以证明为On，这样就可以维护出来凸包P上的向量所对应的在凸包M上的点。因为包含关系，满足所有的向量的对应点都应该在向量的左侧，那么我们将这个向量相对于这个点的坐标求出来，然后维护一个半平面交是否有解即可，判断这个半平面交维护出来的是否是一个合法的凸包，当然由于我们是逆时针枚举的向量，需要先对凸包P进行逆时针转动，所以我们没必要将这些相对于坐标的向量排序，直接维护半平面交，但是最后我们需要判断维护出来的凸包是否严格按照逆时针旋转，因为位置是相对的，可能出现一个向下的向量的左侧是一个向上的向量，这样的关系是矛盾的。

注意细节，由于我的模板用的是求直线交点，精度比较差，eps开的比较小。

 //        ——By DD_BOND

 //#include<bits/stdc++.h>

 //#include<unordered_map>

 //#include<unordered_set>

 #include<functional>

 #include<algorithm>

 #include<iostream>

 //#include<ext/rope>

 #include<iomanip>

 #include<climits>

 #include<cstring>

 #include<cstdlib>

 #include<cstddef>

 #include<cstdio>

 #include<memory>

 #include<vector>

 #include<cctype>

 #include<string>

 #include<cmath>

 #include<queue>

 #include<deque>

 #include<ctime>

 #include<stack>

 #include<map>

 #include<set>

 #define fi first

 #define se second

 #define MP make_pair

 #define pb push_back

 #pragma GCC optimize(3)

 #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

 typedef long long ll;

 using namespace std;

 const int MAXN=1e5+;

 const double eps=1e-;

 const double pi=acos(-1.0);

 const ll INF=0x3f3f3f3f3f3f3f3f;

 inline int dcmp(double x){

     if(fabs(x)<eps)    return ;

     return (x>? : -);

 }

 inline double sqr(double x){ return x*x; }

 struct Point{

     double x,y;

     Point(){ x=,y=; }

     Point(double _x,double _y):x(_x),y(_y){}

     void input(){ scanf("%lf%lf",&x,&y); }

     void output(){ printf("%.2f %.2f\n",x,y); }

     bool operator <(const Point &b)const{

         return (dcmp(x-b.x)==? dcmp(y-b.y)< : x<b.x);

     }

     double operator ^(const Point &b)const{        //叉积

         return x*b.y-y*b.x;

     }

     double operator *(const Point &b)const{        //点积

         return x*b.x+y*b.y;

     }

     bool operator ==(const Point &b)const{

         return dcmp(x-b.x)==&&dcmp(y-b.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 a){

         return Point(x*a,y*a);

     }

     Point operator /(double a){

         return Point(x/a,y/a);

     }

     double len2(){    //长度平方

         return sqr(x)+sqr(y);

     }

     double len(){   //长度

         return sqrt(len2());

     }

 };

 inline double cross(Point a,Point b){    //叉积

     return a.x*b.y-a.y*b.x;

 }

 inline double dot(Point a,Point b){    //点积

     return a.x*b.x+a.y*b.y;

 }

 struct Line{

     Point s,e;

     Line(){}

     Line(Point _s,Point _e):s(_s),e(_e){}

     Point operator &(const Line &b)const{     //求两直线交点

         Point res=s;

         double t=((s-b.s)^(b.s-b.e))/(((s-e)^(b.s-b.e))+eps);

         res.x+=(e.x-s.x)*t;

         res.y+=(e.y-s.y)*t;

         return res;

     }

 };

 int relation(Point p,Line l){    //点和向量关系   1:左侧   2:右侧   3:在线上

     int c=dcmp(cross(p-l.s,l.e-l.s));

     if(c<)    return ;

     else if(c>)    return ;

     else    return ;

 }

 bool counter_wise(Point *p,int n){            //多边形点集调整为逆时针顺序

     for(int i=;i<n-;i++)

         if(dcmp(cross(p[i]-p[i-],p[i+]-p[i-]))>)    return ;

         else if(dcmp(cross(p[i]-p[i-],p[i+]-p[i-]))<){

             reverse(p,p+n);

             return ;

         }

     return ;

 }

 Point tmp[MAXN];

 int convex_hull(Point *p,int n,Point *ch){    //求凸包

     int m=;

     sort(p,p+n);

     for(int i=;i<n;i++){

         while(m>&&dcmp(cross(tmp[m-]-tmp[m-],p[i]-tmp[m-]))<=)    m--;

         tmp[m++]=p[i];

     }

     int k=m;

     for(int i=n-;i>=;i--){

         while(m>k&&dcmp(cross(tmp[m-]-tmp[m-],p[i]-tmp[m-]))<=)    m--;

         tmp[m++]=p[i];

     }

     if(n>)    m--;

     for(int i=;i<m;i++)    ch[i]=tmp[i];

     return m;

 }

 Line que[MAXN];

 int half_plane_intersection(Line *L,int n){    //以逆时针方向 半平面交求多边形的核  ch表示凸包的顶点  返回顶点数 -1则表示不存在

     int head=,tail=;

     que[]=L[],que[]=L[];

     for(int i=;i<n;i++){

         while(tail>head&&relation(que[tail]&que[tail-],L[i])==)   tail--;

         while(tail>head&&relation(que[head]&que[head+],L[i])==)   head++;

         que[++tail]=L[i];

     }

     while(tail>head&&relation(que[tail]&que[tail-],que[head])==)  tail--;

     while(tail>head&&relation(que[head]&que[head+],que[tail])==)  head++;

     for(int i=head;i<=tail;i++){

         int j=(i==tail? head: i+);

         if(dcmp(cross(que[i].e-que[i].s,que[j].e-que[j].s))<=)

             return ;

     }

     return ;

 }

 Line line[MAXN];

 Point p[MAXN],q[MAXN],ops[MAXN];

 int main(void){

     int T;  scanf("%d",&T);

     while(T--){

         int n;  scanf("%d",&n);

         for(int i=;i<n;i++)    p[i].input();

         int m;  scanf("%d",&m);

         for(int i=;i<m;i++)    q[i].input();

         counter_wise(p,n);  m=convex_hull(q,m,q);

         double ans=INF;

         for(int t=;t<=;t++){

             for(int i=;i<n;i++)    p[i]=Point(-p[i].x,-p[i].y);

             for(int i=,j=;i<n;i++){

                 while(dcmp(cross(p[(i+)%n]-p[i],q[(j-+m)%m]-q[j]))<||dcmp(cross(p[(i+)%n]-p[i],q[(j+)%m]-q[j]))<)   j=(j+)%m;

                 ops[i]=q[j];

             }

             double l=,r=1e10;

             for(int i=;i<;i++){

                 double mid=(l+r)/;

                 for(int j=;j<n;j++)    line[j]=Line(p[j]*mid-ops[j],p[(j+)%n]*mid-ops[j]);

                 if(half_plane_intersection(line,n)) r=mid;

                 else    l=mid;

             }

             ans=min(ans,l);

         }

         printf("%.10lf\n",ans);

     }

     return ;

 }

巴特西

HDU 6617 Enveloping Convex（凸包+半平面交+二分）

最新文章

热门文章