poj 1106 Transmitters (枚举+叉积运用)

题目链接：http://poj.org/problem?id=1106

 

算法思路：由于圆心和半径都确定，又是180度，这里枚举过一点的直径，求出这个直径的一个在圆上的端点，就可以用叉积的大于，等于，小于0判断点在直径上，左，右。 这里要记录直径两边的加直径上的点的个数，去最大的。

 

代码：

#include<cstdio> #include<cstring> #include<cmath> #include<iostream> #include<algorithm> #include<queue> using namespace std;const double eps = 1e-8; const double PI = acos(-1.0); const double INF = 1000000000000000.000;struct Point{double x,y;Point(double x=0, double y=0) : x(x),y(y){ } //构造函数 }; typedef Point Vector;struct Circle{Point c;double r;Circle() {}Circle(Point c,double r): c(c),r(r) {} }; Vector operator + (Vector A , Vector B){return Vector(A.x+B.x,A.y+B.y);} Vector operator - (Vector A , Vector B){return Vector(A.x-B.x,A.y-B.y);} Vector operator * (double p,Vector A){return Vector(A.x*p,A.y*p);} Vector operator / (Vector A , double p){return Vector(A.x/p,A.y/p);}bool operator < (const Point& a,const Point& b){return a.x < b.x ||( a.x == b.x && a.y < b.y); }int dcmp(double x){if(fabs(x) < eps) return 0;else return x < 0 ? -1 : 1; } bool operator == (const Point& a, const Point& b){return dcmp(a.x - b.x) == 0 && dcmp(a.y - b.y) == 0; }///向量（x,y）的极角用atan2(y,x); inline double Dot(Vector A, Vector B){ return A.x*B.x + A.y*B.y; } inline double Length(Vector A) { return sqrt(Dot(A,A)); } inline double Angle(Vector A, Vector B) { return acos(Dot(A,B) / Length(A) / Length(B)); } double Cross(Vector A, Vector B) { return A.x*B.y - A.y * B.x; } Vector vecunit(Vector v){ return v / Length(v);} //单位向量 Point read_point(){Point A;scanf("%lf %lf",&A.x,&A.y);return A; }//多边形 //求面积 double PolygonArea(Point* p,int n){ //n个点double area = 0;for(int i=1;i<n-1;i++){area += Cross(p[i]-p[0],p[i+1]-p[0]);}return area/2; }/*************************************分 割 线*****************************************/int main() {//freopen("E:\\acm\\input.txt","r",stdin); Point O,P[155];double R;while(scanf("%lf %lf %lf",&O.x,&O.y,&R) == 3 && dcmp(R)>0){int N;cin>>N;int cnt = 0;for(int i=1;i<=N;i++){Point temp = read_point();double len = Length(temp-O);if(dcmp(len-R) > 0) continue;P[++cnt] = temp;}int ans = 0;for(int i=1; i<=cnt; i++){if(P[i] == O){ans = max(ans,1);continue;}int lnum = 1;int rnum = 1;Vector v = P[i] - O;v = (-1.0)*vecunit(v);Point T = O + R*v;for(int j=1; j<=cnt; j++){if(i == j) continue;if(dcmp(Cross(P[j]-T,O-T)) > 0 ) lnum++;else if(dcmp(Cross(P[j]-T,O-T)) == 0) lnum++,rnum++;else rnum++;}int num = max(lnum,rnum);ans = max(ans,num);}printf("%d\n",ans);} } View Code

 

转载于:https://www.cnblogs.com/acmdeweilai/p/3352748.html

总结

以上是生活随笔为你收集整理的poj 1106 Transmitters (枚举+叉积运用)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。