B - Space Bowling
Time Limit: 20 Sec
Memory Limit: 256 MB
题目连接
http://acm.hust.edu.cn/vjudge/contest/view.action?cid=87643#problem/B
Description
The inhabitants of planets orbiting around the pulsar PSR 2010+15 enjoy playing space bowling. A few cylindrical pins of unit diameter are set on a huge field. A player chooses a certain point of the field and rolls a ball from this point, trying to destroy as many pins as possible. After the ball is released, it rolls in a straight line, touching the surface all the time before rolling away from the field. If the ball touches a pin, this pin dematerializes, and the ball doesn't change direction. To score a strike, the player has to destroy at least k pins in one shot.
Unfortunately, aliens haven't yet invented a machine that would return the balls that rolled away from the field. Instead, they use a machine that materializes a new ball from vacuum before each shot. A player enters the diameter and in a second he obtains a ball of exactly the same diameter.
It is time for an alien Vas-Vas to roll a ball. There are n pins standing on the field at the moment. Help Vas-Vas to determine the minimal diameter of a ball, he can score a strike with.
Input
The first line contains space-separated integers n and k (1 ≤ k ≤ n ≤ 200) . The i-th of following n lines contains space-separated integersxi and yi (−10 5 ≤ xi, yi ≤ 10 5) , which are the coordinates of the centers of pins. All pins are situated at different points.
Output
Output the minimal possible diameter of a ball which can be used to score a strike, with absolute or relative error not exceeding 10 −6. If a strike can be scored with a ball of arbitrarily small diameter, output “0.000000”.
Sample Input
5 4
0 4
0 6
6 4
6 6
3 0
Sample Output
1.0000000000
HINT
题意
平面上有n个直径为1的圆，然后让你飞出一个球，要求触碰至少k个圆，问这个球的半径至少为多少
题解：
直接暴力枚举两个圆，然后直线方向就是这两个圆的中垂线，然后暴力算距离，取第k大的就好了
有一些小细节
代码前面都是模板，无视就好了
代码：
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <complex>
#include <vector>
using namespace std; const double eps = 1e-; //精度控制
const double pi = acos(-); int dcmp(double p) // 三态比较, 负数返回 -1 ， 0 返回 0 ， 正数返回 1
{
if (fabs(p) < eps) return ;
else return p < ? - : ;
} inline double Deg2Rad(const double & p) // 角度转弧度
{
return pi*p/180.0;
} inline double Rad2Deg(const double & p) // 弧度转角度
{
return p * 180.0 / pi;
} struct Point
{
long long x , y ;
Point (double x = . , double y = .)
{
this->x = x , this->y = y;
}
//***********重载函数*****************
friend Point operator + (const Point & T1, const Point & T2)
{
return Point(T1.x + T2.x , T1.y + T2.y);
}
friend Point operator - (const Point & T1, const Point & T2)
{
return Point(T1.x - T2.x , T1.y - T2.y);
}
friend Point operator * (const Point & T1 , const double p)
{
return Point(T1.x * p , T1.y * p);
}
friend Point operator * (const Point & T1 , const int p)
{
return Point(T1.x * p , T1.y * p);
}
friend bool operator == (const Point & T1 , const Point & T2) // 三态比较，精度较高
{
return dcmp(T1.x - T2.x) == && dcmp(T1.y - T2.y) == ;
}
friend ostream& operator << (ostream & os,const Point & x)
{
os << "x is " << x.x << " y is " << x.y;
return os;
}
//************************************
}; typedef Point Vector;
double Dot(const Vector & T1 , const Vector & T2)
{
return T1.x * T2.x + T1.y * T2.y;
} double Length(const Vector & T1)
{
return sqrt(Dot(T1,T1));
} double Angle(const Vector & T1 , const Vector & T2)
{
return acos(Dot(T1,T2)/ Length(T1) / Length(T2));
} double Cross(const Vector & T1, const Vector & T2)
{
return T1.x * T2.y - T2.x * T1.y;
} double Area2(const Point & T1 , const Point & T2, const Point & T3)
{
return Cross(T3-T1,T2-T1);
} // 将T1向量绕着起点逆时针旋转 rad 弧度
Vector Rotate(const Vector & T1 , const double rad)
{
return Vector(T1.x*cos(rad) - T1.y * sin(rad) , T1.x*sin(rad) + T1.y*cos(rad));
} // 返回向量T1的单位向量,调用时确保向量长度不为 0
Vector Normal(const Vector & T1)
{
double L = Length(T1);
return Vector(T1.x/L,T1.y/L);
} bool cmp1(const Point & a,const Point & b)
{
return a.x < b.x || (dcmp(a.x-b.x) == && a.y < b.y);
} //按照极角排序
bool cmp2(const Point & a,const Point & b)
{
double t1 = atan2(a.y,a.x);
double t2 = atan2(b.y,b.x);
if (t1 < ) t1 += 360.0;
if (t2 < ) t2 += 360.0;
return t1 < t2;
} // 点 A 到 点 u 和点 v 组成的直线的距离
double DistanceToLine(const Point & A , const Point & u , const Point &v)
{
Vector v1(A-u) , v2(v-u);
return fabs(Cross(v1,v2)) / Length(v2);
} double DistanceToSegment(const Point & A,const Point & u,const Point & v)
{
if (u == v) return Length(A-u);
Vector v1 = v - u , v2 = A - u , v3 = A - v;
if (dcmp(Dot(v1,v2)) < ) return Length(v2);
else if(dcmp(Dot(v1,v3)) > ) return Length(v3);
else return fabs(Cross(v1,v2)) / Length(v1);
} // 求两直线交点 , Line A上一点a , 向量 va , Line B上一点 b ,向量vb
Point GetLineIntersection(const Point & a , const Vector & va, const Point & b , const Vector & vb)
{
Vector u = a-b;
double t = Cross(vb, u) / Cross(va, vb);
return a+va*t;
} // 规范相交判断
bool SegmentProperIntersection(const Point & a1,const Point & a2,const Point & b1,const Point & b2)
{
double c1 = Cross(b2-b1,a1-b1) , c2 = Cross(b2-b1,a2-b1) , c3 = Cross(a2-a1,b1-a1) , c4 = Cross(a2-a1,b2-a1);
return dcmp(c1) * dcmp(c2) < && dcmp(c3) * dcmp(c4) < ;
} // 判断点p是否在 a1 和 a2构成的线段上( 不包括端点 )
bool IsPointOnSegment(const Point & p,const Point & a1 , const Point & a2)
{
return dcmp(Cross(a1-p,a2-p)) == && Dot(a1-p,a2-p) < ;
} // Pay attention !!!
// 下面的多边形函数带入的多边形点集必须全部为多边形上的点 ， 且 必须已经按照极坐标排序(逆时针) // 返回凸包的面积，p 必须全部是凸包上的点
double ConvexPolygonArea(Point * Polygon , int n)
{
double area = ;
for(int i = ; i < n - ; ++ i) area += Cross(Polygon[i]-Polygon[],Polygon[i+]-Polygon[]);
return area / 2.0;
} // 复杂度 O(n)
// 点在多边形内的判断
int PointInPolygon(const Point & p,const Point * Polygon,const int n)
{
int wn = ;
for(int i = ; i < n ; ++ i)
{
int t1 = i;
int t2 = (i+) >= n ? i+-n : i+;
if (IsPointOnSegment(p,Polygon[t1],Polygon[t2])) return -; // 点在多边形边界上
int k = dcmp(Cross(Polygon[t2] - Polygon[t1],p - Polygon[t1]));
int d1 = dcmp(Polygon[t1].y - p.y);
int d2 = dcmp(Polygon[t2].y - Polygon[t1].y);
if (k > && d1 <= && d2 > ) wn ++;
if (k < && d2 <= && d1 > ) wn --;
}
if (wn != ) return ; //在多边形内部
return ; // 外部
} //********************************************************************************************** // 计算凸包
// 输入的p数组不允许有重复点
// 如果不希望在凸包的边上有输入点，把两个<= 该成 <
// 精度要求较高时用dcmp
int ConvexHull(Point * p , int n , Point * ch)
{
sort(p,p+n,cmp1);
int m = ;
for(int i = ; i < n ; ++ i)
{
while(m > && Cross(ch[m-] - ch[m-] , p[i] - ch[m-]) <= ) m --;
ch[m++] = p[i];
}
int k = m;
for(int i = n - ; i >= ; -- i)
{
while(m > k && Cross(ch[m-] - ch[m-] , p[i] - ch[m-]) <= ) m --;
ch[m++] = p[i];
}
if (n > ) m--;
return m;
} const int maxn = 2e2 + ;
int n , k ,cot;
Point p[maxn];
long long pos[maxn]; int main(int argc,char *argv[])
{
double ans = 1e200;
scanf("%d%d",&n,&k);
if (n == )
{
printf("0\n");
return ;
}
for(int i = ; i < n ; ++ i) scanf("%I64d%I64d",&p[i].x,&p[i].y);
for(int i = ; i < n ; ++ i)
for(int j = ; j < n ; ++ j)
{
// if (i == j) continue;
long long dx = p[j].y - p[i].y;
long long dy = p[i].x - p[j].x;
long long c = dx * p[i].x + dy * p[i].y;
int cur = ;
for(int kk = ; kk < n ; ++ kk)
{
long long d = dx * p[kk].x + dy*p[kk].y;
if (d - c >= )
{
pos[cur++] = d-c;
}
}
if (cur >= k)
{
sort(pos,pos+cur);
ans = min(ans , (double)pos[k-] / sqrt(dx*dx + dy*dy));
}
}
if (dcmp(ans-1.00) <= ) ans = 0.0;
else ans -= 1.00;
printf("%.10lf\n",ans);
return ;
}