【♂Not The Triumph♂O(∩_∩)O哈哈~But The Struggle♂】

竞赛决不是捷径,它只是另一种艰辛的生活方式。得到与失去,只有时间会去评判;成功与失败,只有历史能去仲裁。我不会永远成功,正如我不会永远失败一样

  C++博客 :: 首页 :: 联系 ::  :: 管理
  6 Posts :: 239 Stories :: 25 Comments :: 0 Trackbacks

常用链接

留言簿(7)

我参与的团队

搜索

  •  

积分与排名

  • 积分 - 108806
  • 排名 - 230

最新评论

阅读排行榜

评论排行榜

“我该怎么办?”飞行员klux向你求助。
事实上,klux面对的是一个很简单的问题,但是他实在太菜了。
klux要想轰炸某个区域内的一些地方,它们是位于平面上的一些点,但是(显然地)klux遇到了抵抗,所以klux只能飞一次,而且由于飞机比较破,一点起飞就只能沿直线飞行,无法转弯。现在他想一次轰炸最多的地方。

input:
输入数据由n对整数组成(1<n<700),每对整数表示一个点的坐标。没有一个点会出现两次。

output:
一个整数,表示一条直线能覆盖的最多的点数。

input:
5
1 1
2 2
3 3
9 10
10 11

output:
3

分析:
      简单的计算几何题目,利用了直线方程式(同一直线上任意点都满足方程式)
      直线的方程我们先看看两点式方程:
      (y-y1)/(y2-y1)=(x-x1)/(x2-x1)
      交叉相乘并整理可以得到:(y-y1)(x2-x1)=(y2-y1)(x-x1)
       化为一般式:ax+by+c=0 得:

     其中:
     A=y2-y1
     B=x2-x1
    C=-ax1+by1

    这样就可以尽量避免除法,因为众所周知,除法是很费时间的,而且有精度问题。
    再一次枚举n个点,找出最多。

【参考程序】:  

#include<stdio.h>
#include
<stdlib.h>
#include
<string.h>
using namespace std;
struct point
{
    
int x,y;
};
point p[
710];
int n,i,j,max,ans;
int main()
{
    scanf(
"%d",&n);
    
for (i=1;i<=n;i++) scanf("%d%d",&p[i].x,&p[i].y);
    ans
=0;
    
for (i=1;i<=n-1;i++)
      
for (j=i+1;j<=n;j++)
      {
            max
=0;
            
int a,b,c;
            a
=p[j].y-p[i].y;
            b
=p[j].x-p[i].x;
            c
=-a*p[i].x+b*p[i].y;
            
for (int k=1;k<=n;k++)
              
if (a*p[k].x-b*p[k].y+c==0)
                max
++;
            
if (ans<max) ans=max;
      }
    printf(
"%d\n",ans);
    system(
"pause");
    
return 0;
}
posted on 2009-03-29 09:07 开拓者 阅读(339) 评论(0)  编辑 收藏 引用 所属分类: 数论&几何

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理