首页 > 其他分享 >【题解】[APIO2010] 信号覆盖

【题解】[APIO2010] 信号覆盖

时间:2023-03-28 09:23:23浏览次数:43  
标签:return 覆盖 Point int 题解 APIO2010 180 quad 多边形

题目分析:

其实就是涉及四个点之间的位置关系,三个点形成圆判断是否包含另一个点。
考虑四个点之间形成的多边形只可能是凸四边形或者是凹四边形,如下图所示:

(上图为凸多边形)

(上图为凹多边形)

因为题目保证不存在四点共圆,也就是说对于任意一个四边形不存在对角之和为 \(180°\),也就是一定存在一组对角其和大于 \(180°\),而另一组小于 \(180°\),所以必然有点满足在另外三点构成的圆上。
如上图凸多边形所示则 \(B\) 一定在 \(ADC\) 所构成的圆上,\(D\) 一定在 \(ABC\) 构成的圆上,因为对角之和大于 \(180°\) 就一定在圆内。
如上图凹多边形所示则 \(C\) 一定在 \(ABD\) 所构成的圆上,原因同理。
所以我们的就可以得到,设 \(x\) 为凸多边形的数量,\(y\) 为凹多边形的数量,答案即:

\[2\times x + y \]

对于计数而言,显然凹多边形容易计数,因为他有独特的凹角,只要求出凹角的数量就可以得到凹多边形的数量。但是个人习惯而言凸角比凹角好求一些,因为凸角就是小于 \(180°\) 的角。
所以可以考虑对于每一个点极角排序,然后枚举一定含有哪一条边,那么能与这一条边形成一个凸角的边必然在一个连续的区间内,就可以直接使用双指针维护。极角排序如下图所示:

(其实也就是按照逆时针顺序访问每一个点)
所以直接顺着推回去就可以得到答案了。

代码:

点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 3005;
struct Point{
	int x,y;
}S,a[N],b[N];
int n;
Point operator - (Point a,Point b){return {a.x-b.x,a.y-b.y};}
Point operator + (Point a,Point b){return {a.x+b.x,a.y+b.y};}
int quad(Point a){return (a.x < 0) ^ (3 * (a.y < 0));}
bool cmp(Point a,Point b){
	if(quad(a) == quad(b))	return (a.x * b.y - a.y * b.x) > 0;
	return quad(a) < quad(b);
}
bool check(Point a,Point b){   //判断 a -> b 夹角是否小于 180° 
	return a.x * b.y - a.y * b.x > 0;
}
int binom(int n,int m){
	if(n < 0 || m < 0 || n < m)	return 0;
	int ans = 1;
	for(int i=n-m+1; i<=n; i++)	ans = ans * i;
	for(int i=1; i<=m; i++)	ans = ans / i;
	return ans;
}
int get(Point S){
	int tot = 0,ans = 0;
	for(int i=1; i<=n; i++){
		if(a[i].x == S.x && a[i].y == S.y)	continue;
		b[++tot] = a[i] - S;
	}
	sort(b+1,b+tot+1,cmp);
	for(int i=1; i<=tot; i++)	b[i+tot] = b[i];   //记得开二倍啊啊啊啊啊啊啊 
	int now = 2;
	for(int i=1; i<=tot; i++){
		if(now == i)	now = i + 1;
		while(check(b[i],b[now]))	now++;
		ans += binom(now - i - 1,2);
	}
	return ans;
}
signed main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	scanf("%lld",&n);
	for(int i=1; i<=n; i++)	scanf("%lld%lld",&a[i].x,&a[i].y);
	int ans1 = 0;
	for(int i=1; i<=n; i++){
		S = a[i];
		ans1 += get(S);  //求凸角的个数 
	}
	int ans2 = 4 * binom(n,4) - ans1; //求凹角/凹多边形个数
	int ans3 = binom(n,4) - ans2;//求凸多边形的个数 
	int ans = ans2 + ans3 * 2;//求答案 
	printf("%.3f\n",1.0 * ans / binom(n,3) + 3);//别忘了选择的三个点也叫在圆上 
	return 0;
}

标签:return,覆盖,Point,int,题解,APIO2010,180,quad,多边形
From: https://www.cnblogs.com/linyihdfj/p/17263749.html

相关文章

  • 【题解】Atcoder ABC295 A-G
    A.ProbablyEnglish题目分析:直接每一个单词判一下就好了。代码:点击查看代码#include<bits/stdc++.h>usingnamespacestd;intmain(){ intn;scanf("%d",&n); bo......
  • CF743B Chloe and the sequence 题解 分治
    题目链接:http://codeforces.com/problemset/problem/743/B题目大意:对于一个n-序列,如果n==0,那么它是一个空的序列(也就是说空序列中没有元素)。然后会进行i次操作,每次......
  • CF768B Code For 1 题解 分治
    题目链接:http://codeforces.com/problemset/problem/768/B解题思路:分治。本题和的解题思路相似。tips:如果如果\(n\)对应的区间完全被\([l,r]\)覆盖了,则区间\([......
  • leetcode-841-钥匙和房间 题解
    题目描述有N个房间,开始时你位于0号房间。每个房间有不同的号码:0,1,2,...,N-1,并且房间里可能有一些钥匙能使你进入下一个房间。在形式上,对于每个房间i都有一个钥匙列表r......
  • 【LeetCode滑动窗口专题】水果成篮 + 最小覆盖子串(hard)
    二刷刷到滑动窗口,发现有一些细节和遗漏,在此补充实际上关于滑动窗口的题还有一题:最小长度的子数组进入正题水果成篮LeetCode904水果成篮你正在探访一家农场,农场从左到......
  • 【ACM算法竞赛日常训练】DAY4题解与分析【树】【子序列】| 组合数学 | 动态规划
    DAY4共2题:树(组合数学)子序列(dp,数学)......
  • C#中重写(override)及覆盖(new)的区别详解
    1.重写和覆盖的定义1.1重写(override)的定义  在C#中,用override关键字来重写一个父类中的虚方法或抽象方法。override关键字用于指示编译器,我要用派生类中的一个方法......
  • 「题解」ABC290F Maximum Diameter
    没动脑子就gf一路写下来了......实际上就是把插板法的gf写了一下/zk首先考虑一下一个\(X\)合法是什么情况,那就是总和是\(2n-2\)并且保证\(0<X_i<n\)。证明就考......
  • 变量覆盖--duomicms通杀漏洞
    下载源码本地测试然后进行代码审计发现这个地方可能存在变量覆盖:/duomiphp/common.php查看包含了common.php的地方先看看后台登录的地方,调......
  • [ABC295Ex] E or m 题解
    状压dp,2hd4me/ng。题意开始你有一个全\(0\)矩阵,你可以随意执行如下操作:选择任意一行,将其从最左端开始的连续一段染成\(1\)。选择任意一列,将其从最上端开始的连......