[比赛][二分][计算集合][定长圆最大点覆盖] 2018 ICPC 沈阳网络赛 E The cake is a lie

比赛的时候一看计算几何直接跳过了,其实不是不可以做。。。

这个里面,各个草莓的半径其实对计算影响不大,由于圆的对称性,只要求出能覆盖s个草莓的圆心的最小圆就可以了,输出答案时加上草莓的半径r即可。

然后求定长圆的最大点覆盖就是有点模板了,有两种算法,n^3和n^2logn的,但是既然是抄板子那肯定是抄最快的了。。。

#include 
using namespace std;

#define Mn 305
const double eps = 1e-7;
const double pi = acos(-1.0);
#define sqr(x) ((x) * (x))
struct Point
{
	double x,y;
	Point() {}
	Point(double tx,double ty)
	{
		x=tx;
		y=ty;
	}
} p[Mn+5];
struct Node
{
	double angle;
	bool in;
} arc[Mn * Mn + 5];
int n;
double dist(Point p1,Point p2)
{
	return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
}
bool cmp(Node &n1,Node &n2)
{
	return n1.angle2.0*R) continue;

            double angle=atan2(p[i].y-p[j].y,p[i].x-p[j].x);
            if(angle < 0)
                angle += 2 * pi;

            double phi=acos(D/(2.0*R));
            arc[cnt].angle=angle-phi+ 2 * pi;arc[cnt++].in=true;
            arc[cnt].angle=angle+phi+ 2 * pi;arc[cnt++].in=false;
        }
        sort(arc,arc+cnt,cmp);
        int tmp=1;
        for(int j=0;jeps)
		{
			double mid=(l1+r1)*0.5;
			R=mid;
			int p=MaxCircleCover();
			if(p>=s)
			{
				r1=mid;
			}
			else
			{
				l1=mid;
			}
		}
		printf("%.4lf\n",l1+r);
	}
	return 0;
}

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据