hdu 6617 Enveloping Convex

貌似数据是错的。。不管数据对不对，至少这是个比较强的计算几何。

题意：给定n个点的凸多边形A，需要找到最小的与A相似的多边形A’，并且A’与A的对应边平行，使得A’包含平面上m个点。输出最小的相似比。

显然先对m个点凸包，然后二分相似比。然后要判断凸包A能否包含凸包B。一个观察是临界情况B的一条边卡着A的两条边，可以枚举卡的边来确定相对位置，判断其他点是否在A内部，需要旋转卡壳来加速。不幸的是数据范围比较大，算交点时会有很大的精度误差。正确做法比较直接，先算出A的边在B上对应的点，然后做个差向内平移一段距离，半平面交判断是否为空即可。(既然有闵科夫斯基和，当然也有差了2333)

一个坑点是与A中心对称的图形也满足条件，所以还要翻过来再算一次。

```
#include<bits/stdc++.h>
```
```
using namespace std;
```
```
 
```
```
#define inc(i,n) for (int i=0;i<n;i++)
```
```
 
```
```
typedef double db;
```
```
const db PI=acos(-1);
```
```
const db eps=1e-11, inf=1e12;
```
```
 
```
```
bool eq(db x){return fabs(x)<eps;}
```
```
int sgn(db x){
```
```
    if (x<=-eps) return -1;
```
```
    return x>=eps;
```
```
}
```
```
 
```
```
#define Vec const vec &
```
```
#define Point const point &
```
```
struct vec{
```
```
    db x,y;
```
```
    vec():x(0),y(0){}
```

    vec(db x, db y):x(x),y(y){} //[i] init-list is easier to use in c++1x

    vec(db theta):x(cos(theta)),y(sin(theta)){}

```
 
```

    bool operator==(Vec v) const{return eq(x-v.x) && eq(y-v.y);}

```
    db ang() const{return atan2(y,x);}
```
```
 
```

    vec operator+(Vec v) const{return vec(x+v.x,y+v.y);}

    vec operator-(Vec v) const{return vec(x-v.x,y-v.y);}

    vec operator*(db a) const{return vec(x*a,y*a);}

    vec operator/(db a) const{return vec(x/a,y/a);}

```
 
```

    db operator|(Vec v) const{return x*v.x+y*v.y;}

    db operator&(Vec v) const{return x*v.y-y*v.x;}

    db operator!() const{return sqrt(x*x+y*y);}

```
 
```

    bool operator<(Vec v) const{return x==v.x?y<v.y:x<v.x;}

```
 
```
```
    void rd(){scanf("%lf%lf",&x,&y);}
```
```
    void prt(){printf("%f %f\n",x,y);}
```
```
    vec std(){
```
```
        return (*this)/!(*this);
```
```
    }
```

    friend ostream& operator<<(ostream &o, Vec v){return o<<v.x<<','<<v.y;}

```
};
```
```
typedef vec point;
```
```
db cross(Vec a, Vec b, Vec c){
```
```
    return b-a&c-a;
```
```
}
```
```
 
```

point lineInt(Point p, Vec vp, Point q, Vec vq){

```
    db t=(vq & p-q)/(vp&vq);
```
```
    return p+vp*t;
```
```
}
```
```
 
```

int convex(point *p, int n, point *ans){

```
    sort(p,p+n);
```
```
    int m=0;
```
```
    for (int i=0;i<n;i++){
```

        while (m>1 && cross(ans[m-2],ans[m-1],p[i])<=eps) m--;

```
        ans[m++]=p[i];
```
```
    }
```
```
    int k=m;
```
```
    for (int i=n-2;i>=0;i--){
```

        while (m>k && cross(ans[m-2],ans[m-1],p[i])<=eps) m--;

```
        ans[m++]=p[i];
```
```
    }
```
```
    if (n>1) m--; //p[0]==p[m]
```
```
    return m;
```
```
}
```
```
 
```
```
const int N=100010;
```
```
 
```

point p[N],q0[N],q[N],p0[N],q1[N],vl,vr;

```
int n,m;
```
```
 
```
```
struct line{
```
```
	point p; vec v;
```
```
};
```
```
 
```

bool onleft(point p, const line &l){return sgn(l.v&p-l.p)>0;}

```
line Q[N<<1]; //deque of lines
```

point T[N<<1]; //deque of points(result)

```
bool halfplaneInt(line *l, int n){
```

	int head=0,tail=0; //rangeof Q:[head,tail] ; range of T: [head, tail)

```
	Q[0]=l[0];
```
```
	for (int i=1;i<n;i++){
```

		while (head<tail && !onleft(T[tail-1],l[i])) tail--;

		while (head<tail && !onleft(T[head],l[i])) head++;

```
		Q[++tail]=l[i];
```

		if (eq(Q[tail].v&Q[tail-1].v)){ //same direction

```
			--tail;
```

			if (onleft(l[i].p,l[i])) Q[tail]=l[i]; //replace righter line

```
		}
```
```
		if (head<tail) //get point
```

			T[tail-1]=lineInt(Q[tail-1].p,Q[tail-1].v,Q[tail].p,Q[tail].v);

```
	}
```

	while (head<tail && !onleft(T[tail-1],Q[head])) tail--;

	if (head>=tail-1) return 0;  //m<3, no available area

```
	return 1;
```
```
}
```
```
 
```
```
line pl[N];
```
```
bool chk(db r){
```
```
    for (int i=0;i<n;i++){
```
```
    	vec v1=p[i]*r-q1[i];
```
```
    	vec v2=p[i+1]*r-q1[i];
```
```
    	pl[i]={v1,v2-v1};
```
```
	}
```
```
    return halfplaneInt(pl,n);
```
```
}
```
```
 
```
```
int main(){
```
```
	//freopen("14160.in","r",stdin);
```
```
    int T; scanf("%d",&T);
```
```
    while (T--){
```
```
        scanf("%d",&n);
```
```
        db gmax=0;
```

        inc(i,n) p0[i].rd(),gmax=max(gmax,max(p0[i].x,p0[i].y));

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

        inc(i,m) q0[i].rd(),gmax=max(gmax,max(q0[i].x,q0[i].y));

        //inc(i,n) p0[i]=p0[i]/gmax; inc(i,m) q0[i]=q0[i]/gmax;

        n=convex(p0,n,p); m=convex(q0,m,q);

```
        p[n]=p[0];
```
```
        /*
```
```
        int mpi; db mpd=10;
```
```
        for (int i=0;i<n;i++){
```

            db diff=fabs((p[i+1]-p[i]).ang()-(p[i]-p[(i+n-1)%n]).ang());

```
            if (diff<mpd){
```
```
                mpd=diff;
```
```
                mpi=i;
```
```
            }
```
```
        }
```
```
        rotate(p,p+mpi,p+n);*/
```
```
        q[m]=q[0];
```
```
        q[m+1]=q[1];
```
```
        p[n]=p[0];
```
```
        db ans1=1e10;
```
```
		for (int _=0;_<2;_++){
```
```
			for (int i=0,des=0;i<n;i++){
```

				while (!((p[i+1]-p[i]&q[des+1]-q[des])>=0 && (p[i+1]-p[i]&q[des]-q[(des-1+m)%m])<=0)) des=(des+1)%m;

```
				q1[i]=q[des];
```
```
			}
```
```
	        db l=1e-7, r=1e8;
```
```
	        for (int i=0;i<60;i++){
```
```
	            db mid=(l+r)/2;
```
```
	            if (chk(mid)) r=mid;
```
```
	            else l=mid;
```
```
	        }
```
```
	        ans1=min(ans1,l);
```
```
			inc(i,n+1) p[i]=(vec){0,0}-p[i];
```
```
		}
```
```
        printf("%.10lf\n",ans1);
```
```
    }
```
```
    return 0;
```
```
}
```

fffasttime

hdu 6617 Enveloping Convex

发表评论取消回复

发表评论 取消回复

发表评论取消回复