加载中…
个人资料
abentu
abentu
  • 博客等级:
  • 博客积分:0
  • 博客访问:15,867
  • 关注人气:4
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
相关博文
推荐博文
谁看过这篇博文
加载中…
正文 字体大小:

poj1648-Countryside Highway

(2010-07-15 13:16:04)

  一个很规则的格点阵被一条直线穿过,问直线穿过了几个格子。其中即便这条直线只擦到了边角也算它穿过了这个格子。

  用高中解析几何学的线性规划解就可以了,设直线为ax+by+c=0,然后检验各个方格的四个顶点关于这个直线是否同号即可,当且仅当同号才会不被穿过。

 

水过~~

 

代码:


#include "stdio.h"
#include "math.h"
#define N 110

int n,w,e,result;

int main()
{
 freopen("3.txt","r",stdin);

 int i,j,x,y,t1,t2,t3,t4;
 while (scanf("%d%d%d",&n,&w,&e) != EOF && n > 0)
 {

  if (w == e)
  {
   if (w == 0 || w == 100 * N)
    printf("%d\n",n);
   else if (w % 100 == 0)
    printf("%d\n",2 * n);
   else
    printf("%d\n",n);
   break;
  }

  //线性规划的表达式为(e-w)*x - 100 * n * y + 100 * n * w

  result = 0;

  for (i = 1;i <= n;i ++)
  for (j = 1;j <= n;j ++)
  {
   x = 100 * i - 100;
   y = 100 * j - 100;
   t1 = (e-w)*x - 100 * n * y + 100 * n * w;
   x = 100 * i;
   y = 100 * j - 100;
   t2 = (e-w)*x - 100 * n * y + 100 * n * w;
   x = 100 * i - 100;
   y = 100 * j;
   t3 = (e-w)*x - 100 * n * y + 100 * n * w;
   x = 100 * i;
   y = 100 * j;
   t4 = (e-w)*x - 100 * n * y + 100 * n * w;

   if (!((t1>0 && t2>0 && t3>0 && t4>0) || (t1<0 && t2<0 && t3<0 && t4<0)))
    result ++;
  }

  printf("%d\n",result);

 }

 return 0;
}

 

 

 

 

 

0

阅读 评论 收藏 转载 喜欢 打印举报/Report
  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

      

    新浪BLOG意见反馈留言板 电话:4000520066 提示音后按1键(按当地市话标准计费) 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有