差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:legal_string:组队训练比赛记录:contest8 [2021/07/29 22:04]
王智彪
+++ 2020-2021:teams:legal_string:组队训练比赛记录:contest8 [2021/07/31 23:50] (当前版本)
lgwza [补题情况]
@@ 行 4: / 行 4: @@
 ^  题目  ^  蒋贤蒙  ^  王赵安  ^  王智彪  ^
-|  D  |  2  |  0  |  0  |
+|  D  |  2  |  0  |  1  |
-|  E  |  0  |  0  |  0  |
+|  E  |  0  |  1  |  2  |
-|  L  |  0  |  0  |  2  |
+|  L  |  0  |  1  |  2  |
 ====== 题解 ======
@@ 行 87: / 行 87: @@
 }
 </code>
+</hidden>
+===== E. Enclosure =====
+==== 题意 ====
+给定 $k$ 个点，作为初始的区域，对于剩下的 $n-k$ 个点，我们选择一个加入到现在这个区域，求构成的新的区域最大面积（当然区域的面积就是凸包的面积了）。
+数据范围： $3≤k＜n≤100,100$ ，坐标绝对值不超过 $10^{9}$ 。
+==== 题解 ====
+思路来的很快，刚看这道题的时候，显然先求一下 $k$ 个点的凸包，然后对于剩下的 $n-k$ 个点，可能极角排序一下然后在哪二分一下？找到相当于是这个点到凸包的两条切线的交点，然后求一下面积，单个复杂度是 $O(logn)$ 的，然后 $n-k$ 个点，大概就是 $O(nlogn)$ 可以通过，事实证明，真的有队伍这么过，但是我当时 $zz$ 了，并不知道在哪里找二分的点（听说是在凸包里找一个点作为极角排序的那个点，大概重心？开始胡诌 $…$ ）。
+来说说正解，正解是我推翻了上个想法之后两分钟就想到的，显然最大面积的点一定是总图形的凸包上的顶点，因为其他任意的点由几何知识可以知道到某边距离一定不大于这条边被大凸包“包围”的那两个点到这条边距离的最大值，然后求一下三角形面积就知道了。
+对于最开始选的一个点，我们可以暴力找到上述两条切线的交点，一个设为 $l$ ，一个设为 $r$ ，然后我们对于大凸包上的点开始转，容易发现， $l$ 和 $r$ 也会跟着转（其实就是双指针啦），这样转一圈总复杂度是 $O(n)$ 的（应该没口胡错 $×$ ）。至于面积，我们可以发现新增的面积肯定是 $l$ 和 $r$ 和放进来的点构成的三角形减去 $l$ 到 $r$ 直接构成的多边形，显然我们在转的时候可以动态维护 $l$ 和 $r$ 之间的这个多边形的面积，用三角剖分搞一下就可以了，然后对于三角形，直接求面积就可以了，这样单次维护面积的复杂度是 $O(1)$ 的，总复杂度还是 $O(n)$ 。
+然后这题细节很多，首先肯定要用 $long long$ ，而不能用 $double$ ，否则第二个点都过不去 $×$ 。然后我暴力找的那个点我想让他找的准，所以对于小凸包（就是 $k$ 个点构成的凸包）上的点，我直接 $continue$ 了，然后有可能真的没找到这个符合规范的点，就直接输出小凸包面积就可以了，因为忘了这茬，所以在第三个数据那里 $re$ 了...然后就 $ac$ 了，撒花~
+<hidden 代码>
+<code cpp>
+int n,k;
+int main() {
+	scanf("%d %d",&n,&k);
+	for(int i=0; i<k; i++) {
+		scanf("%lld %lld",&PO.p[i].x,&PO.p[i].y);
+		PO.p[i].id=i+1;//这里标记一下哪些是小凸包的点
+		PO1.p[i]=PO.p[i];
+	}
+	PO.n=k;
+	PO1.n=n;
+	PO.Graham(po);
+	Point ptmp;
+	int p1,p2;
+	for(int i=k; i<n; i++) {
+		scanf("%lld %lld",&PO1.p[i].x,&PO1.p[i].y);
+	}
+	PO1.Graham(po1);
+	ll ans=po.getarea();//先求一下小凸包面积
+	ll tans=0;
+	int l=-1,r=-1;
+	int pp=-100;
+	for(int i=0;i<po1.n;i++) {
+		if(po1.p[i].id) {
+			continue;
+		}
+		pp=i;
+		break;
+	}
+	if(pp==-100) {//这里要特判没有外面点的情况，也就是大小凸包重合，没有算下去的必要。
+		printf("%lld.%d\n",ans>>1,ans%2==0?0:5);
+		return 0;
+	}
+	for (int i=0; i<po.n;i++) {//暴力求第一个的l,r指针
+		if ((l==-1)||(((po.p[i]-po1.p[pp])^(po.p[l]-po1.p[pp]))<=0)) {
+			l=i;
+		}
+		if ((r==-1)||(((po.p[i]-po1.p[pp])^(po.p[r]-po1.p[pp]))>=0)) {
+			r=i;
+		}
+	}
+	ll ts=0;
+	for(int i=l;i!=r;i=(i+1)%po.n) {
+		ts+=((po.p[i])^(po.p[(i+1)%po.n]));//暴力算一下多边形面积
+	}
+	ts+=(po.p[r]^po.p[l]);//三角剖分算回来
+	tans=max(tans,labs((po1.p[pp]^po.p[l])+(po.p[r]^po1.p[pp])+(po.p[l]^po.p[r]))-labs(ts));//先求这个点的最大值 三角形面积-多边形面积
+	for(int i=pp+1;i<po1.n;i++) {
+		while((!(po.p[r]==po1.p[i]))&&((po.p[(r+1)%po.n]-po1.p[i])^(po.p[r]-po1.p[i]))>=0) {
+			ts-=(po.p[r]^po.p[l]);//都是三角剖分
+			ts+=(po.p[r]^po.p[(r+1)%po.n]);
+			ts+=(po.p[(r+1)%po.n]^po.p[l]);
+			r=(r+1)%po.n;
+		}
+		while((!(po.p[l]==po1.p[i]))&&((po.p[(l+1)%po.n]-po1.p[i])^(po.p[l]-po1.p[i])) <= 0) {
+			ts-=(po.p[r]^po.p[l]);//都是三角剖分
+			ts-=(po.p[l]^po.p[(l+1)%po.n]);
+			l=(l+1)%po.n;
+			ts+=(po.p[r]^po.p[l]);
+		}
+		tans=max(tans,labs((po.p[l]^po1.p[i])+(po1.p[i]^po.p[r])+(po.p[r]^po.p[l]))-labs(ts));
+	}
+	printf("%lld.%d\n",(ans+tans)>>1,(ans+tans)%2==0?0:5);
+	return 0;
+}
+</code>
 </hidden>

CVBB ACM Team

用户工具

站点工具

差别

页面工具