首页 > 其他分享 >SP898 Transmitters 题解

SP898 Transmitters 题解

时间:2023-05-25 22:13:45浏览次数:31  
标签:ch Transmitters int 题解 SP898 long double 半圆 define

Description

给定 \(n\) 个点的坐标、半圆的半径以及坐标。问半圆怎么放能覆盖最多的点,输出最多个数。

Solution

计算几何入门题。

首先显然距离圆心超过半径的点是一定不会被覆盖的,舍去。

再者我们考虑,半圆的放法是有无限多种的,我们要考虑哪些是有用的。我们可以想到,最优的半圆一定刚好卡上一个点,这样就能留充足的空间给别的点。因为 \(n\leq150\),所以可以暴力枚举边界,然后用叉积统计一边的点的个数,这样另一边点的个数就是总点数减去这一边点的个数,取个 \(\max\) 统计一下即可。

Code

#include<bits/stdc++.h>
//#define int long long
#define ll long long
#define next nxt
#define re register
#define il inline
const int N = 1e5 + 5;
const double eps = 1e-6;
const double Pi = acos(-1.0);
using namespace std;

struct Point{
	double x,y;
}a[N],p[N],o;
int n,cnt,ans,Max;
double R;

il int read()
{
	int f=0,s=0;
	char ch=getchar();
	for(;!isdigit(ch);ch=getchar()) f |= (ch=='-');
	for(; isdigit(ch);ch=getchar()) s = (s<<1) + (s<<3) + (ch^48);
	return f ? -s : s;
}

Point operator +(Point a,Point b) { return Point{a.x+b.x,a.y+b.y}; }//加

Point operator -(Point a,Point b) { return Point{a.x-b.x,a.y-b.y}; }//减

il double operator *(Point a,Point b) { return a.x*b.y - a.y*b.x; }//叉积

il double operator &(Point a,Point b) { return a.x*b.x + a.y*b.y; }//点积

il double cross(Point a,Point b,Point c) { return (b-a)*(c-a); }//判断c和直线ab的关系 

il double len(Point a) { return sqrt(a&a); }

il double dis(Point a,Point b) { return len(b-a); }

il void Main()
{
	scanf("%lf%lf%lf",&o.x,&o.y,&R);
	if(R < 0) exit(0);
	n = read();
	cnt = Max = ans = 0;
	for(re int i=1;i<=n;i++)
	{
		scanf("%lf%lf",&a[i].x,&a[i].y);
		if(dis(a[i],o) <= R) p[++cnt] = a[i];//保留有用的
	}
	n = cnt;
	for(re int i=1;i<=n;i++)//枚举边界
	{
		ans = 0;
		for(re int j=1;j<=n;j++)
			if(cross(o,p[i],p[j]) <= 0) ans++;//统计一边
		Max = max(Max,max(ans,n-ans));
	}
	cout << Max << "\n";
}

signed main()
{
	while(1) Main();
	return 0;
}

复杂度 \(O(Tn^2)\),可以通过本题。

标签:ch,Transmitters,int,题解,SP898,long,double,半圆,define
From: https://www.cnblogs.com/bloodstalk/p/17433106.html

相关文章

  • P8943 Deception Point 题解
    Description题目给的很详细了。Solution首先\(n\)个点\(n\)条边,我们很容易就想到基环树(比正常的树多了一条边,形成了一个环),不会也没关系,这题跟基环树其实关系不大。首先,我们可以发现题目中说明了这个环不是一个四元及以下的环,这代表着如果\(A\)提前进入了这个环,那么他......
  • [ABC287D] Match or Not 题解
    Description翻译给的很明白了,就是让你判断\(S\)串的前\(x(0\leqx\leq|T|)\)个字符和后\(|T|-x\)个字符组成的字符串和\(T\)串是否相等,其中问号能代替所有字母。Solution很有意思的一道题。首先我们可以知道,如果前\(i-1\)位不能匹配的话,那么第\(i\)位不管它本......
  • P5446 [THUPC2018]绿绿和串串 题解
    Description给定一个串\(S\),要求串\(S\)是串\(R\)经过多次翻转后的前缀。问有多少种初始长度的串\(R\)。串\(R\)翻转的定义是将前\(|R|-1\)个字符倒序排列后,插入到串的最后。如\(\mathrm{aaa}\)翻转后得到\(\mathrm{abcdcba}\)。Solution我们先设以\(i\)为......
  • CF1139E Maximize Mex 题解
    Description\(n\)个学生,\(m\)个社团。每个学生有一个能力值,且仅属于一个社团。这\(d\)天内,每天从\(m\)个社团中选人,使得选出的人的能力值的\(\text{mex}\)最大。每天会有一个人在选人之前退团。\(d,m\leqn\leq5000\)Solution巧妙建图题。首先,我们可以很显然的......
  • P8081 [COCI2011-2012#4] ZIMA 题解
    题意给定一个长度为\(n\)的序列。当连续\(T\)天温度都小于\(0\)时,则称这\(T\)天为一个冰期,冰期来临之前的\(2T\)天都被标记为警示状态.特殊地,如果一个冰期最长,那么它的前\(3T\)天会被标记为警示状态。如果有多个冰期最长,选一个。思路模拟预处理出每个冰期的长......
  • AT2395 [ARC071C] TrBBnsformBBtion 题解
    题目大意有两个只包含\(A\)和\(B\)的字符串,给出两种操作A可以变为BB,B可以变为A;AAA可以消去,BBB也可以消去。思路找规律。这里我们以A为主,将B全部变为A。因为可以无限次操作,那么就代表如果两个字符串可以相等,那么他们就一定能够经过转化后变成同一个字......
  • CF714B Filya and Homework 题解
    题意给定一个长度为\(n\)的数组。我们可以给一些数加上一个\(x\),也可以减去一个\(x\),也可以不加也不减。问:是否存在一个数\(x\),使得这个数组里各个数都相等。思路一道思维题首先考虑,在这个数组中,相同的元素,我们一定是给它做相同的操作,否则一定不相等,根据这个思想,......
  • UVA1514 Piece it together 题解
    图论题还是在于建图题意给定一个长度为\(n\timesm\)的网格图,有的地方是白方块,有的是黑方块,有的啥也没用。给你如下四种\(L\)形方块,询问是否存在方法,让这些方块正好就是给出的图的形状。$L$形方块如下思路二分图首先我们要想,为什么需要二分图:若能拼成,那么就说......
  • SP15637 Mr Youngs Picture Permutations 题解
    题意给定一个最多有\(5\)排的一个队伍,每一个位置对应一个同学,给定总人数和第\(i\)排要站\(n_i\)个人。要求每行左边的同学身高要大于右边的,每列从上往下要从大到小。问:满足要求的一共有多少种方案。思路DP首先考虑,在这个题目中,有用的状态有每列最后的人的高度,每行......
  • P8584 探索未知 题解
    题意给你\(n\)个分数,每个分数后面跟着一个操作符\(op\),如果为\(1\)就是加上这个分数,是\(2\)就减去。初始时是\(0\),询问\(n\)次操作后最后的分数是多少,化成最简分数。特殊地,如果最后是个整数,直接以整数的形式输出。思路模拟考试的时候一看就想到了[NOIP2020]......