POJ1106->叉积判断点在直线的左右

POJ1106->叉积判断点在直线的左右

题意：

给定平面上一些点的坐标，有一个半径固定，圆心固定且可以旋转的半圆形平面，求这个平面能覆盖到的最大点的数量。

题解：

由于圆心半径一定，所以有效的点的坐标即是在这个圆形区域内的点的坐标，可以开个数组记录一下，之后可以通过枚举圆心和这些有效点构成的直线，并通过叉乘来统计每次在这条直线左侧的点的数量来更新答案。

代码：

#include <stdio.h>
#include <iostream>
#include <cmath>
#include<algorithm>
using namespace std;
#define
MAX 50005
const double eps = 1e-8;
double r;
int sgn(double x)
{
if (fabs(x) < eps) return 0;
if (x < 0) return -1;
else return 1;
}
struct Point
{
double x, y;
Point() {}
Point(double _x, double _y)
{
x = _x; y = _y;
}
Point operator - (const Point &b) const
{
return Point(x - b.x, y - b.y);
}
int operator ^ (const Point &b) const
{
return x*b.y - y*b.x;
}
int operator * (const Point &b) const
{
return x*b.x + y*b.y;
}
};
struct Line
{
Point s, e;
Line() {}
Line(Point _s, Point _e)
{
s = _s; e = _e;
}
};
Point point[MAX];
double xmult(Point p0, Point p1, Point p2) //叉积p0p1 X p0p2
{
//cout << ((p1 - p0) ^ (p2 - p0)) << endl;
return (p1 - p0) ^ (p2 - p0);
}
bool dist(double x, double y)
{
double d = (point[0].x - x)*(point[0].x - x) + (point[0].y - y)*(point[0].y - y);
//cout << "d:" << d << endl;
if (d < r * r || fabs(d - r * r) < eps)
return true;
return false;
}
int main()
{
double x, y;
while (scanf("%lf%lf%lf", &x, &y, &r) != EOF)
{
if (r < 0) break;
//cout <<"r:"<< r*r << endl;
int n, cnt = 1, ans = 0, temp;
point[0].x = x;
point[0].y = y;
scanf("%d", &n);
while (n--)
{
scanf("%lf%lf", &x, &y);
if (dist(x, y))
{
point[cnt].x = x;
point[cnt++].y = y;
}
}
for (int i = 1; i < cnt; i++)
{
temp = 1;
Line line = Line(Point(point[0].x, point[0].y), Point(point[i].x, point[i].y));
for (int j = 1; j < cnt; j++)
{
//cout << xmult(point[i],line.s, line.e) << endl;
if (j != i && xmult(line.s, line.e,point[j] ) <= 0)
temp++;
}
ans = max(ans, temp);
}
printf("%dn", ans);
}
return 0;
}

最后

以上就是默默大山为你收集整理的POJ1106->叉积判断点在直线的左右的全部内容，希望文章能够帮你解决POJ1106->叉积判断点在直线的左右所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。