用户工具

站点工具


2020-2021:teams:legal_string:组队训练比赛记录:contest9

这是本文档旧的修订版!


比赛链接

补题情况

题目 蒋贤蒙 王赵安 王智彪
A 0 0 0
B 0 0 0
C 0 0 0
D 0 0 0
E 0 0 0
F 0 0 2
G 0 0 2
H 0 0 0
I 0 0 0
J 0 0 0

题解

F. Finding Points

题意

给定一个凸包,点按照逆时针给出,然后求凸包内一点,想要这个点与这个凸多边形相邻点组成的 $n$ 个角的最小值最大,求这个最大值。 $(4≤n≤100)$

题解

赛场上两分钟出思路,然后看通过率…感觉是不是有坑就没敢写…赛后听说改数据了…血亏!

显然要二分(废话)。

然后对于每一组相邻的点,这个点和这两个点组成的角大于某个角,则这个点一定在这两个点组成的大弓形内,根据圆周角求 $n$ 个圆看面积交即可,然后比赛的时候猜到会有点跑到凸包外面的情况,但是我不会写圆的交再交凸包,这也是我怂了的原因之一,谁知道改数据嘛!

所以就是个板子题…

代码

代码

int N;
Point ppx[110];
int main() {
	scanf("%d",&C.n);
	N=C.n;
	for(int i=0;i<C.n;i++) {
		ppx[i].input();
	}
	ppx[C.n]=ppx[0];
	double l=eps,r=2.0*acos(-1)/N;
	while(r-l>1e-15) {
		double mid=(l+r)/2;
		for (int i=0;i<C.n;i++) {
			C.c[i].r=(ppx[i].distance(ppx[i+1])/2/sin(mid));
			double dtmp=C.c[i].r*cos(mid);
			Point ptmp=(ppx[i]+ppx[i+1])/2;
			Point pptmp=(ppx[i]-ptmp);
			pptmp=pptmp.rotright();
			pptmp=pptmp.trunc(dtmp);
			ptmp=ptmp+pptmp;
			C.c[i].p=ptmp;
		}
		C.getarea();
		if(C.ans[C.n]>1e-20)l=mid;
		else r=mid;
	}
	printf("%.20lf\n",l*180/pi);
	return 0;
}
2020-2021/teams/legal_string/组队训练比赛记录/contest9.1627740182.txt.gz · 最后更改: 2021/07/31 22:03 由 王智彪