[算法刷题题解笔记] POJ 1106 Transmitters [计算几何|叉积|点线关系]

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

3
4
4

#include <iostream>
using namespace std;
int main() {
  // 圆心和半径 
  double circle_x, circle_y, r;
  // 还有测试数据就继续 
  while (cin >> circle_x >> circle_y >> r) {
    if (r < 0) break; // 半径为负数，退出
    int n = 0; // 点的个数 
    cin >> n;
    // 存储在圆内的点 
        // 不知道为什么数组大小写n，动态创建数组，在POJ会报编译异常
    // double xi[n];
    // double yi[n];
        // 所以数组大小直接用字面量了
        double xi[100000];
        double yi[100000];
    int cnt = 0;
    for (int i=0; i<n; i++) {
      // 输入的每个点的坐标 
      double x, y;
      cin >> x >> y;
      // 只保存在圆内的点 
      if ( ((x - circle_x) * (x - circle_x) + (y - circle_y) * (y - circle_y)) <= r * r ) {
        xi[cnt] = x;
        yi[cnt] = y;
        cnt++;
      }
    }
    // 保存答案
    int ans = 0; // 在半圆内的点的最大个数 
    // 以在圆内的每个点为边界进行判断
    // 即直径在当前枚举的点的位置上 
    for (int i=0; i<cnt; i++) {
      double x = xi[i];
      double y = yi[i];
      // 直径向量
      double diameter_x = x - circle_x;
      double diameter_y = y - circle_y; 
      // 记录当前情况下的最大值
      int max_now = 0; 
      // 判断每个点是否在当前枚举的半圆内 
      for (int j=0; j<cnt; j++) {
        // 当前要判断是否在半圆内的点和圆心组成的向量 
        double vector_x = xi[j] - circle_x;
        double vector_y = yi[j] - circle_y; 
        // 通过叉积判断是否在半圆内 
        if ((vector_x * diameter_y) - (vector_y * diameter_x) >= 0) {
          max_now++;
        } 
      } 
      // 和另外半边圆的个数比较，取较大值 
      max_now = max_now > (cnt - max_now) ? max_now : (cnt - max_now);
            // 更新答案
      ans = ans < max_now ? max_now : ans;
    }
    cout << ans << endl; 
  }
}