代碼比較長(zhǎng)，寫(xiě)蹉了……
#include <iostream>
#include <algorithm>
#include <math.h>
#include <string.h>
#define eps 1e-7
using namespace std;
struct point{double x, y, angle, dis;};
int sig(double a)
{return (a > eps) - (a < -eps);}
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 cross(point a,point b,point c)
{return (a.x - c.x)*(b.y - c.y) - (a.y - c.y)*(b.x - c.x);}
double mul(point a, point b)
{return a.x*b.x + a.y*b.y;}
double mod(point a)
{return a.x*a.x + a.y*a.y;}
double jiajiao(point a, point b)
{
if(!sig(mul(a,b)-(mod(a)*mod(b)))) return 0;
return acos(mul(a,b)/sqrt(mod(a)*mod(b)));
}
bool cmp(point a, point b)
{
return !sig(a.angle-b.angle) && sig(a.dis-b.dis)<0 || sig(a.angle-b.angle)<0;
}
point m0[1001], m1[1001], h0[1001], h1[1001], ray, base;
int len0, len1, id0[1001], id1[1001];
//m1 m2 原始點(diǎn)集 h1 h2凸包 ray基準(zhǔn)向量 base基準(zhǔn)點(diǎn)
//len[0]是 h[0]的長(zhǎng)度
int n;
void read()
{
for(int i = 0; i < n; i ++)
scanf("%lf %lf", &m0[i].x, &m0[i].y);
for(int i = 0; i < n; i ++)
scanf("%lf %lf", &m1[i].x, &m1[i].y);
}
void tubao0()
{
point a = m0[0];
int j = 0, i;
for(i = 1; i < n; i ++)
if(m0[i].y==a.y&&m0[i].x<a.x || m0[i].y<a.y)
{
j = i;
a = m0[i];
}
swap(m0[0] , m0[j]);
m0[0].angle = 0;
for(i = 1; i < n; i ++)
{
m0[i].angle = atan2(m0[i].y - m0[0].y, m0[i].x - m0[0].x);
m0[i].dis = dist(m0[0], m0[i]);
}
sort(m0 + 1, m0 + n, cmp);
int top = 0;
id0[0] = n - 1;
h0[top ++] = m0[n-1];
id0[1] = 0;
h0[top ++] = m0[0];
if( sig( m0[1].angle - m0[n-1].angle ) == 0 )
{
id0[top] = 1;
h0[top ++] = m0[1];
}
else
{
for(i = 1;i < n; i ++)
{
if(sig(cross(m0[i], h0[top-2], h0[top-1])) > 0)
{
id0[top] = i;
h0[top ++] = m0[i];
}
else
{
top --;
i --;
}
}
}
len0 = top;
}
void tubao1()
{
point a = m1[0];
int j = 0, i;
for(i = 1; i < n; i ++)
if(m1[i].y==a.y&&m1[i].x<a.x || m1[i].y<a.y)
{
j = i;
a = m1[i];
}
swap(m1[0] , m1[j]);
m1[0].angle = 0;
for(i = 1; i < n; i ++)
{
m1[i].angle = atan2(m1[i].y - m1[0].y, m1[i].x - m1[0].x);
m1[i].dis = dist(m1[0], m1[i]);
}
sort(m1 + 1, m1 + n, cmp);
//for(i=0;i<n;i++)printf("%lf %lf\n",m0[i].x,m0[i].y);
int top = 0;
id1[0] = n - 1;
h1[top ++] = m1[n-1];
id1[1] = 0;
h1[top ++] = m1[0];
if( sig( m1[1].angle - m1[n-1].angle ) == 0 )
{
id1[top] = 1;
h1[top ++] = m1[1];
}
else
{
for(i = 1;i < n; i ++)
{
if(sig(cross(m1[i], h1[top-2], h1[top-1])) > 0)
{
id1[top] = i;
h1[top ++] = m1[i];
}
else
{
top --;
i --;
}
}
}
len1 = top;
}
void pre()
{
point tt;
ray.x = h0[2].x - h0[1].x;
ray.y = h0[2].y - h0[1].y;
swap(m0[id0[1]], m0[0]);
m0[0].angle = 0;
m0[0].dis = 0;
for(int i = 1; i < n; i ++)
{
tt.x = m0[i].x - m0[0].x;
tt.y = m0[i].y - m0[0].y;
m0[i].angle = jiajiao(tt, ray);
m0[i].dis = dist(m0[0], m0[i]);
}
sort(m0 + 1,m0 + n, cmp);
}
double enum_()
{
int i, j, flag;
point tray, tbase, tt;
double angle, minans = 9999999;
h1[len1] = h1[0];
for(i = 0; i<= len1; i ++)
{
tray.x = h1[i + 1].x - h1[i].x;
tray.y = h1[i + 1].y - h1[i].y;
angle = jiajiao(tray, ray);
//printf("ray:%lf %lf tray:%lf %lf angle = %lf\n",ray.x,ray.y,tray.x,tray.y,angle);
m1[0].angle = 0;
m1[0].dis = 0;
for(j = 0; j < n; j ++)
{
tt.x = m1[j].x - h1[i].x;
tt.y = m1[j].y - h1[i].y;
m1[j].angle = jiajiao(tt, tray);
m1[j].dis = dist(h1[i], m1[j]);
}
sort(m1, m1 + n, cmp);
//for(j=0;j<n;j++)printf("%lf %lf\n",m1[j].x,m1[j].y); puts("");
//for(j=0;j<n;j++)printf("%lf %lf\n",m0[j].x,m0[j].y); puts("");
flag = 0;
for(j = 1; j < n; j ++)
{
//printf("%lf %lf %lf %lf\n",m0[j].angle,m1[j].angle,m0[j].dis,m1[j].dis);
if(sig(m0[j].angle - m1[j].angle) || sig(m0[j].dis - m1[j].dis))
{
flag = 1;
break;
}
}
//printf("%d\n",flag);
if(!flag)
{
double xx = jiajiao(tray, ray);
if(sig(minans - xx) > 0) minans = xx;
}
}
return minans;
}
int main()
{
double ans;
int i;
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
while(scanf("%d", &n) , n)
{
read();
if(n == 1)
{
double x = 0;
printf("%.10lf\n",x);
continue;
}
if(n == 2)
{
point a, b, c;
a.x = m0[0].x - m0[1].x; a.y = m0[0].y - m0[1].y;
b.x = m0[1].x - m0[0].x; b.y = m0[1].y - m0[0].y;
c.x = m1[0].x - m1[1].x; c.y = m1[0].y - m1[1].y;
printf("%.10lf\n",min(jiajiao(a,c),jiajiao(b,c)));
continue;
}
tubao0();
tubao1();
//for(i=0;i<=len0;i++)printf("%lf %lf\n",h0[i].x,h0[i].y);
//for(i=0;i<=len1;i++)printf("%lf %lf\n",h1[i].x,h1[i].y);
pre();
ans = enum_();
printf("%.10lf\n",ans);
}
//while(1);
}