SSL 1232 雷达覆盖

---

题目

Description

以雷达心为圆心的半圆形雷达覆盖范围有多个点 雷达可旋转，求最多覆盖数（含在边界的）

Input
多组数据
每组数据第一行有两个整数和一个实数，分别为雷达坐标与半径
第二行为一个整数 n ，表示点数
接下来 n 行，每行两个整数表示点坐标
当半径为负数时，即雷达出现错误，多组数据结束

Output
每组数据输出一行，为题目答案，即雷达最多覆盖数

Sample Input

25 25 3.5
7
25 28
23 27
27 27
24 23
26 23
24 29
26 29
350 200 2.0
5
350 202
350 199
350 198
348 200
352 200
995 995 10.0
4
1000 1000
999 998
990 992
1000 999
100 100 -2.5

Sample Output

3
4
4 

Hint
来源：zju

---

解题思路

基本概念

---

首先可以很容易将雷达不可能达到的点排出去，与雷达坐标距离超过半径

枚举雷达的边覆盖哪个点，即以哪个点为边

比如黄点与雷达中心划线，以这条线为雷达边边旋转
然后就是用叉积判断其它点方向，负的和正的分成两边，正负覆盖点取max
注意叉积为零时，也就是在雷达边上，即算负也算正

---

Code

#include <iostream>
#include <cstdio>
#include <cmath>
#define N 100000using namespace std;int X, Y, n, num, k, le, ri, ans;
int x[N + 200], y[N + 200];
double r;int main() {scanf("%d %d %lf", &X, &Y, &r);while(r > 0) {scanf("%d", &n);num = ans = 0;for(int i = 1; i <= n; i ++) {++ num;scanf("%d %d", &x[num], &y[num]);if(sqrt((x[num] - X) * (x[num] - X) + (y[num] - Y) * (y[num] - Y)) > r)num --;}for(int i = 1; i <= num; i ++) {le = ri = 0;for(int j = 1; j <= num; j ++) {k = (x[i] - X) * (y[j] - Y) - (x[j] - X) * (y[i] - Y);if(k >= 0) le ++;if(k <= 0) ri ++;}ans = max(ans, max(le, ri));}printf("%d\n", ans);scanf("%d %d %lf", &X, &Y, &r);}
}