题意：
有一个多边形，提问m个圆，求圆被多边形完全包含需要移动的最少距离。
题解：
做过的一道目前最难的几何题，充分发挥了暴力的思想。
看到这个问题的第一想法就是，多边形向内缩R（圆的半径），然后求圆心到缩小的多边形的最短距离即可。方法就是枚举新的多边形的线段，求点到线段的最短距离。
那么我们的目标就成了求新的多边形，但细思极恐......
最理想的情况是这样：
但是，这样：
这样：
都是可以的，因为下图的虚线部分才是到实线距离为R的边界
那么我们发现，缩小的多边形的边界是有很多块的，而且每块都是直线与圆弧的混合，自闭了。。。。
10s的时限加才200的范围怎么利用起来呢？
换个方向，我们从新的边界入手。
我们知道边界是这样的：
那么最小值一定在边界的：
1.线段上
2.圆弧上
3.线段与圆弧的交点上
4.线段与线段的交点上
但是我们的思想之前被“边界”给束缚了，就是说我们之前只是想光考虑边界上的点，因为边界显然是最优的！
但是，显然也是最麻烦的！
我们要重复发挥暴力的思想。
我们已经知道正解就存在于以上四种情况中，当然，边界也在那4种情况中，我们现在抛弃边界，求出所有的直线与直线的交点、直线与圆的交点，点到直线的投影，这些点有很多很多无效的点（在边界外或者距离多边形的最小距离小于R），但没关系啊，正解也在就可以了！
我们将所有点都检查一遍，去除在边界外或者距离多边形的最小距离小于R的点，然后就是点到点的距离了。
jls讲的，真的暴力。。。
代码：
#include<bits/stdc++.h>
#define N 210
#define INF 0x3f3f3f3f
#define eps 1e-5
#define pi 3.141592653589793
#define LL long long
#define pb push_back
#define cl clear
#define si size
#define lb lowwer_bound
#define mem(x) memset(x,0,sizeof x)
#define sc(x) scanf("%d",&x)
#define scc(x,y) scanf("%d%d",&x,&y)
#define sccc(x,y,z) Iscanf("%d%d%d",&x,&y,&z)
using namespace std;
int cmp(double x){if (fabs(x)<eps)return 0;else return x<0?-1:1;}
int T,n,m; double R;
struct Point
{
double x,y;
bool operator < (const Point &a)const
{return cmp(x-a.x)<0 || (cmp(x-a.x)==0 && cmp(y-a.y)<0);}
Point(double x=0,double y=0):x(x),y(y){ }
}a[N];
typedef Point Vector;
Vector operator + (Vector a,Vector b){return Vector(a.x+b.x,a.y+b.y);}
Vector operator - (Vector a,Vector b){return Vector(a.x-b.x,a.y-b.y);}
Vector operator * (Vector a,double b){return Vector(a.x*b,a.y*b);}
Vector operator / (Vector a,double b){return Vector(a.x/b,a.y/b);}
bool operator == (Vector a,Vector b){return cmp(a.x-b.x)==0 && cmp(a.y-b.y)==0;}
double Dot(Vector a,Vector b){return a.x*b.x+a.y*b.y;} //点积
double Length(Vector a){return sqrt(Dot(a,a));}
double Angle(Vector a,Vector b){return acos(min(1.0,max(-1.0,Dot(a,b)/Length(a)/Length(b))));}// 范围[0,180]
double Cross(Vector a,Vector b){return a.x*b.y-a.y*b.x;} //叉积
Vector Rotate(Vector a,double rad)// 向量 a 逆时针旋转 rad
{return Vector(a.x*cos(rad)-a.y*sin(rad),a.x*sin(rad)+a.y*cos(rad));}
struct Circle
{
Point c;
double r;
Circle(Point c=Point(0,0), double r=0):c(c),r(r){}
Point point(double a)
{
return Point(c.x+cos(a)*r,c.y+sin(a)*r);
}
};
struct Line {
Point p;
Vector v;
Line(Point p, Vector v) : p(p), v(v){}
};
//点在线段上（包含端点），在为 1 ，不在为 0
bool isPointOnSegment(Point P,Point A,Point B)
{
return cmp (Cross(A-P,B-P))==0 && cmp (Dot(A-P,B-P))<=0; // 不包含端点时为 <0
}
int isin(Point p)
{
int wn=0;
for(int i=0;i<n;i++)
{
if(isPointOnSegment(p,a[i],a[i+1])) return -1;//在边界上
int k=cmp(Cross(a[i+1]-a[i], p-a[i]));
int d1=cmp(a[i].y-p.y);
int d2=cmp(a[i+1].y-p.y);
if(k>0 && d1<=0 && d2>0) wn++;
if(k<0 && d2<=0 && d1>0) wn--;
}
if(wn!=0) return 1; //在内部
return 0; //在外部
}
//点p到直线ab的距离
double PTL(Point p,Point a,Point b)
{
Vector v1=b-a,v2=p-a;
return fabs(Cross(v1,v2)/Length(v1));
}
//点到线段的距离,p到线段ab的距离，若距离不存在，返回pa，pb中较短的线段的距离
double DTS(Point p,Point a,Point b)
{
if (a==b)return Length(p-a);
Vector v1=b-a,v2=p-a,v3=p-b;
if (cmp(Dot(v1,v2))<0)return Length(v2);
else if (cmp(Dot(v1,v3))>0)return Length(v3);
else return fabs(Cross(v1,v2))/Length(v1);
}
//直线交点
Point GLI(Point p,Vector v,Point q,Vector w)
{
Vector u=p-q;
double t=Cross(w,u)/Cross(v,w);
return p+v*t;
}
//点到直线ab的投影
Point GetLineProjection(Point p,Point a,Point b)
{
Vector v=b-a;
return a+v*(Dot(v,p-a)/Dot(v,v));
}
bool check(Point x)
{
if (isin(x)!=1) return false;
for (int i=0;i<n;i++) if (cmp(DTS(x,a[i],a[i+1])-R)<0) return false;
return true;
}
//直线和圆的交点，返回交点个数，结果存在sol中。
int LCI(Line L, Circle C, vector<Point>& sol) {
double a = L.v.x, b = L.p.x - C.c.x, c = L.v.y, d = L.p.y - C.c.y;
double e = a*a + c*c, f = 2*(a*b + c*d), g = b*b + d*d - C.r*C.r;
double delta = f*f - 4*e*g;
double t1,t2;
if(cmp(delta) < 0) return 0; //相离
if(cmp(delta) == 0) { //相切
t1 = t2 = -f / (2*e);
sol.push_back(L.p+L.v*t1);
return 1;
}
//相交
t1 = (-f - sqrt(delta)) / (2*e); sol.push_back(L.p+L.v*t1);
t2 = (-f + sqrt(delta)) / (2*e); sol.push_back(L.p+L.v*t2);
return 2;
}
//向量a的极角(只是为配合两个圆的交点)
double Angle(const Vector& v) {
return atan2(v.y, v.x);
}
//两圆相交，返回交点数目
int CCI(Circle C1, Circle C2, vector<Point>& sol) {
double d = Length(C1.c - C2.c);
if(cmp(d) == 0) {
if(cmp(C1.r - C2.r) == 0) return -1; //两圆完全重合
return 0; //同心圆，半径不一样
}
if(cmp(d - fabs(C1.r - C2.r)) < 0) return 0;
if(cmp(C1.r + C2.r - d) < 0) return 0;
double a = Angle(C2.c - C1.c); //向量C1C2的极角
double da = acos(min(1.0,max(-1.0,(C1.r*C1.r + d*d - C2.r*C2.r) / (2*C1.r*d))));
//C1C2到C1P1的角
Point p1 = C1.point(a-da), p2 = C1.point(a+da);
sol.push_back(p1);
if(p1 == p2) return 1;
sol.push_back(p2);
return 2;
}
vector<Point> v,p;
Point seg[N][2];
int main()
{
sc(T);
while(T--)
{
scc(n,m); scanf("%lf",&R);
for (int i=0;i<n;i++) scanf("%lf%lf",&a[i].x,&a[i].y); a[n]=a[0];
v.clear();
for (int i=0;i<n;i++) // 内缩之后的直线
{
Point v1=a[i+1]-a[i];Point p1=Rotate(v1,pi*0.5);p1=p1/Length(p1)*R;
seg[i][0]=a[i]+p1;seg[i][1]=a[i+1]+p1;
}
for (int i=0;i<n;i++) //所有直线与直线的交点
for (int j=i+1;j<n;j++)
if (cmp(Cross(seg[i][0]-seg[i][1],seg[j][0]-seg[j][1]))!=0)
v.pb(GLI(seg[i][0],seg[i][0]-seg[i][1],seg[j][0],seg[j][0]-seg[j][1]));
for (int i=0;i<n;i++) //所有的圆与圆的交点
for (int j=0;j<n;j++) if (i!=j) CCI(Circle(a[i],R),Circle(a[j],R),v);
for (int i=0;i<n;i++) //所有的直线与圆的交点
for (int j=0;j<n;j++) LCI(Line(seg[i][0],seg[i][0]-seg[i][1]),Circle(a[j],R),v);
sort(v.begin(),v.end());
p.clear();int tm=0; //去重+去除不合法的点
for (int i=0;i<v.size();i++) if (!tm || tm && !(v[i]==p[tm-1]))if(check(v[i])) {p.pb(v[i]);tm++;}
for (int j=0;j<m;j++)
{
Point t;
scanf("%lf%lf",&t.x,&t.y);
if (check(t)) { puts("0"); continue;}
double ans=1e9;
for (int i=0;i<p.si();i++) ans=min(ans,Length(p[i]-t));// 到交点的最短距离
for (int i=0;i<n;i++)
{
Point v1=GetLineProjection(t,seg[i][0],seg[i][1]); //到线段的最短距离
if (Length(t-v1)<ans && check(v1)) ans=min(ans,Length(t-v1));
v1=t-a[i];
v1=v1/Length(v1)*R; //到圆弧的最短距离
if (Length(a[i]+v1-t)<ans && check(a[i]+v1)) ans=min(ans,Length(a[i]+v1-t));
}
printf("%.0f\n", ans);
}
}
}
京公网安备 11010502036488号