采用枚舉。
首先，Ax+By=0必須表示直線，即A、B不能同時為0；另外，要注意到直線不能過輸入中的2N個點；檢測點在直線的哪一側(cè)，只需要簡單的線性規(guī)劃的知識。
以下是我的代碼：
#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 閱讀(499)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：數(shù)學(xué)/數(shù)論