?

Transmitters

?

题目大意：给你一个半圆的圆心跟半径，再给你N个点，半圆可以绕圆心旋转任意角度，求半圆最多可以覆盖的点的个数是多少。

?

解题思路：因为圆心是固定的，就很简单了。先把在圆的覆盖范围内的点找出来，再对这些点循环去找对于每个点来说，跟它在同一侧的点的个数，同侧的点判断就用叉积就可以，当叉积>=0的时候就是同一侧的。

?

代码如下：

?

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #define sqr(x) ((x)*(x)) using namespace std; const double eps = 1e-8; int dcmp(double x) { return x < -eps ? -1 : x > eps; } struct Point { double x, y; } P[155]; double Distance(Point a, Point b){ return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y)); } double xmult(Point a, Point b, Point c) { return (a.x-c.x)*(b.y-c.y)-(a.y-c.y)*(b.x-c.x); } int main() { Point o; double R; int n; while(~scanf(%lf%lf%lf, &o.x, &o.y, &R)) { if(dcmp(R) < 0) { break; } scanf(%d, &n); Point p; int m = 0; for(int i = 0; i < n; ++i) { scanf(%lf%lf, &p.x, &p.y); if(dcmp(Distance(p, o)-R) <= 0) { P[m++] = p; } } int ans = 0; for(int i = 0; i < m; ++i) { int num = 0; for(int j = 0; j < m; ++j) { if(dcmp(xmult(P[i], P[j], o)) >= 0) { num++; } } //printf(p%d = %lf %lf num = %d , i, P[i].x, P[i].y, num); ans = max(ans, num); } printf(%d , ans); } return 0; } 
     
    
   
  

?