UVA 10167 Birthday Cake(判断点在直线的哪边)
题意:
在一个二维平面上,有一个以(0,0)为圆心的圆,现在圆内有很多整点,现在要你找出一条这样直线AX+BY=0,使得所有整点正好在直线的两边。要你输出A和B,且A和B都属于[-500,500]范围。
分析:
由于A和B都是整数且数据范围比较小,所以我们直接枚举A和B的值即可.
一个点如果在AX+BY=0直线上,那么把坐标带入直线值为0.
否则在同一个方向的点的坐标值带入直线方程, 方程的值要么同时>0 要么同时<0. 所以我们只要看点坐标带入直线方程所得的值是否同号就可以判断到底直线两边各有多少个点.
AC代码:
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
const int maxn=100+5;
struct Point
{
int x,y;
}P[maxn];
void find(int n)
{
for(int a=-500; a<=500; ++a)
{
for(int b=-500; b<=500; ++b)
{
if(a==0 && b==0 )continue;
int i,cnt=0;//记录使得AX+BY>0的点数目
for(i=0; i<n; ++i)
{
if(a*P[i].x+b*P[i].y>0) ++cnt;
else if(a*P[i].x+b*P[i].y==0) break;
}
if(i<n) continue;
if(cnt==n/2)
{
printf("%d %d\n",a,b);
return ;
}
}
}
}
int main()
{
int n;
while(scanf("%d",&n)==1 && n)
{
n*=2;
for(int i=0;i<n;++i)
scanf("%d%d",&P[i].x,&P[i].y);
find(n);
}
return 0;
}
分享到:
相关推荐
包含UVA在线OJ系统的绝大部分的示例代码,并都已AC,可在刷题时参考
UVA109的题解,经测试完全正确,还附有题解。
uva272
UVa在我看来是比较全的一个题解,希望能帮助大家。欢迎下载。
有uva刘汝佳文件夹的50道题解,从数据结构开始,以后慢慢上传
1.Uva_base的编译 在编译球队时,则需要在当前球队文件夹下打开终端输入执行以下命令(以下命令都是在root下执行的): ./configure make clean ...在底层代码Uva_base文件夹下打开终端输入:./start.sh
uva最全ac代码
uva531最长公共子序列问题水题,应用简单的dp即可ac有更快速的方法欢迎讨论
uva10755 ac 代码,可以随意更改下载
uva357的栈实现版本
UVA 题目,不是很难,试试吧
《算法竞赛入门经典》UVa配套题目pdf版完整
世界著名大学UVA OJ平台上的题目部分分类,分的不好请原谅。
利用c#语言,完成UVA题目沃尔多夫在哪里
这里面全部为在Uva Online Judge上面的部分题目的解答,里面提供了解答使用的源代码。
这是一支完整的uva球队,包含所有基本模块,初者可在上修改得到自己的球队
uva_trilearn2002 源代码
主要是uvaoj习题相关题目 练习题目
PDF试题
开源项目-codingsince1985-UVa.zip,Been solving UVa Online Judge Problems in Golang for one year (and counting)