题意：给定一个点的坐标和一个圆半径，一个整数n，然后n个点坐标，求以给定点所在半圆能包含的最多点的个数；
思路：枚举半圆直径边界，统计该边界一侧的包含点数，更新最大值；
技巧：使用叉积，能方便的判断两向量的夹角是否小于180度；
#include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std; const double epsi=1e-10; const double pi=acos(-1.0); const int maxn=50005; struct point{ double x,y; point(double xx=0,double yy=0):x(xx),y(yy){} point operator -(const point &op2) const{ //向量相减 return point(x-op2.x,y-op2.y); } double operator ^(const point &op2) const{ //两个点向量的叉积 return x*op2.y-y*op2.x; } }; inline int sign(const double &x){ //判断浮点数正负 if(x>epsi) return 1; if(x<-epsi) return -1; return 0; } inline double sqr(const double &x){ //平方 return x*x; } inline double mul(const point &p0,const point &p1,const point &p2){ //p0p1与p0p2的叉积 return (p1-p0)^(p2-p0); } inline double dis2(const point &p0,const point &p1){ //p0p1向量模的平方 return sqr(p0.x-p1.x)+sqr(p0.y-p1.y); } inline double dis(const point &p0,const point &p1){ //p0p1的向量模 return sqrt(dis2(p0,p1)); } int n; point p[maxn],cp; double r; int main(){ while(scanf("%lf%lf%lf",&cp.x,&cp.y,&r)&&r>=0){ scanf("%d",&n); int ans=0; for(int i=0;i<n;i++) scanf("%lf %lf",&p[i].x,&p[i].y); for(int i=0;i<n;i++){ //枚举边界 int tmp=0; for(int j=0;j<n;j++) //枚举点 if(sign(dis(p[j],cp)-r)!=1) //距离小于半径且在边界同一侧 if(sign(mul(cp,p[i],p[j]))!=-1) tmp++; ans=max(ans,tmp); } printf("%d ",ans); } return 0; }