采用枚举。
首先，Ax+By=0必须表示直线，即A、B不能同时为0；另外，要注意到直线不能过输入中的2N个点；检测点在直线的哪一侧，只需要简单的线性规划的知识。
以下是我的代码：
#include<cstdio>
using namespace std;
const int kMaxn(57);
int main()
{
/*
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
//*/
int n;
while(scanf("%d",&n)==1 && n)
{
int x[kMaxn<<1],y[kMaxn<<1];
for(int i=1;i<=(n<<1);i++)
scanf("%d%d",&x[i],&y[i]);
bool found(false);
int a,b;
for(int i=-500;i<=500 && !found;i++)
for(int j=-500;j<=500 && !found;j++)
{
if(i==0 && j==0)
continue;
bool cannot(false);
for(int k=1;k<=(n<<1);k++)
if(i*x[k]+j*y[k]==0)
{
cannot=true;
break;
}
if(cannot)
continue;
int t(0);
for(int k=1;k<=(n<<1);k++)
if(i*x[k]+j*y[k]<0)
t++;
if(t==n)
{
a=i;
b=j;
found=true;
}
}
printf("%d %d\n",a,b);
}
return 0;
}
posted on 2011-04-18 00:39
lee1r 阅读(475)
评论(0) 编辑 收藏 引用 所属分类:
题目分类：数学/数论